A. Midnight Meal
이 문제는, 특별한 알고리즘을 요구하기 보다는 입/출력에 대한 연습문제라고도 생각할 수 있습니다.
A군과 B군이 매긴 점수의 합이 제일 큰 야식을 계속 갱신시키고 출력하면 됩니다.
데이터 케이스가 여러 개 들어오니 케이스마다 변수 초기화에서 실수만 하지 않으면 쉽게 통과할 수 있는 문제입니다.
B. Ordered
문제의 description은 약간 길지만, 천천히 읽어보면 복잡한 문제는 아닙니다.
입력받은 수열이 어떤 수열인지를 판별하고, 결정된 수열에서 구해야 하는 값 (mean / frequent) 을 찾으면 됩니다.
mean의 경우는 전체를 더한 후 빈도수로 나누면 될 것이고, frequent의 경우에는 각 숫자를 count하여 제일 많이 나온
"갯수"를 세면 됩니다.
mean을 구할 때 "기약분수"로 만들어야 한다는 조건은 분자와 분모의 최대공약수를 구해서 각각 나눠주면 되겠네요.
C. ChessMetric
C번 문제부터는 알고리즘을 어느 정도 공부한 사람들을 타겟으로 맞춘 문제들이었습니다. (약간 난이도가 올라갑니다.)
시작위치에서 끝 위치까지 갈 수 있는 경우가 아주 많기 때문에 (10억 이상도 가능합니다) 모든 경우를 다 구해보는 경우
시간제한을 초과할 수 있습니다. 이 문제는 알고리즘 수업시간에 배우는 "동적 계획법(Dynamic Programming)"을 사용하면
해결할 수 있습니다.
초기에 KingKnight가 있는 위치는 (sx, sy) 입니다. 그리고 우리가 구하고 싶은 것은 "numMoves번 이동한 후 (ex, ey)에
도달하는 경로가 몇 가지나 있는가?" 입니다.
[spoiler="더 보기..."] table[i][j][k] = i번 이동한 후, (j, k) 의 위치에 올 수 있는 경우의 수
[/spoiler]
라고 정의합시다. 이 때 0번 이동한 후 갈 수 있는 곳은 (sx, sy)밖에 없고, 경우도 한 가지 밖에 없습니다. (초기 위치이기 때문에)
그러면 이제 1번 이동한 후 갈 수 있는 곳을 찾아 봅시다. table[1][A][B] 에는 table[0][A - 2][B - 1] 에서 (2, 1)만큼 이동해서 올 수도
있습니다. 또한 table[0][A][B + 1]에서 (0, -1)만큼 이동해서 올 수도 있지요. table[1][A][B]에 올 수 있는 경우는 총 16가지가 있습니
다. (그림에서 파란색으로 색칠된 부분에서 올 수 있습니다.) 다만, 보드 밖에서 뛰어 올 수는 없으니 이런 경우의 처리는 신경써 주
어야 합니다.
table을 계속 채워나가면서, table[numMoves][ex][ey] 값을 출력해 주면 됩니다.
D. Coherence
참가한 사람 중에서 제일 적은 사람이 통과한 문제입니다. 한 번에 맞은 사람도 한 명밖에 없는 까다로운 문제였습니다. :-)
(w, h) size에서 n개를 택하는 문제입니다만. (w, h) size에서 w * h - n 개를 택하는 문제와 솔루션이 같습니다. 이를 고려한 이유는
다음에 설명하는 솔루션의 "세 가지" 형태에 모든 경우를 포함시키기 위해서 입니다.
왼쪽 위에서부터 시작해서 오른쪽으로 차례대로 채워 나간다. 만약 더 이상 오른쪽으로 채워나가지 못하는 경우
다음 줄로 이동하여 반복한다.
왼쪽 위에서부터 시작해서 아래쪽으로 차례대로 채워 나간다. 만약 더 이상 아래쪽으로 채워나가지 못하는 경우
다음 칸(오른쪽)으로 이동하여 반복한다.
왼쪽 위 점을 지나는 사각형 모양을 만든다
우선, 1과 2의 경우는 간단한 수식으로 경계선의 길이를 구할 수 있습니다. (w가 n의 배수인 경우와 그렇지 않은 경우로 나눠서
생각해 보세요) 그리고 3의 경우는 한 변의 길이를 고정시킨다면 다른 한 변의 길이를 구할 수 있기 때문에, 간단하게 체크할 수
있습니다.
E. Tether
이 문제는 알고리즘 문제라기 보다는 어찌보면 수학문제에 가까웠습니다.
A는 염소의 위치이고, B는 사과나무의 위치입니다. |AB|는 위의 식과 같이 구할 수 있습니다.
각각의 나무에 대해 |AB| < L 인 경우가 얼마나 있는지 세 주면 됩니다.
F. HTML Validation
문제가 무려 4 Page나 되는 데다가, string 처리를 해야 하기 때문인지 코딩하는 데 시간이 꽤 필요한 문제입니다.
이런 문제의 경우에는, 입력을 잘게 쪼갠 후에, 제일 먼저 오류가 나는 태그를 찾습니다. (태그 하나에서 여러 개 나는 경우도
존재할 수 있으므로, 이 경우에는 문제에 써 있는 순서대로 체크합니다.)
문제에 써 있는 형식에는 "맞는" 데이터가 입력으로 들어오지만, "상식적이지 않은" 데이터가 들어올 수 있기 때문에,
"당연히 이런 경우는 없겠지" 라는 생각으로 코딩을 하면 말리기 딱 좋은 문제입니다. :-)
astein
옛날부터 쓰려고 맘잡고 있었는게 이제야 의욕이 마구마구 생기네요.
혹시나 대회에 참가하지 못 하셨던 분들을 위해 문제 링크도 걸어둡니다.
http://tanso.kaist.ac.kr/~scudjh/bbs/view.php?id=notice&page=1&sn1=&divpage=1&sn=off&ss=on&sc=on&select_arrange=headnum&desc=asc&no=13
P.S) 소스코드는 내일 중에 올리겠습니다. 깔끔하게 짠 소스를 찾아야 해서 [...]
A. Midnight Meal
이 문제는, 특별한 알고리즘을 요구하기 보다는 입/출력에 대한 연습문제라고도 생각할 수 있습니다.
A군과 B군이 매긴 점수의 합이 제일 큰 야식을 계속 갱신시키고 출력하면 됩니다.
데이터 케이스가 여러 개 들어오니 케이스마다 변수 초기화에서 실수만 하지 않으면 쉽게 통과할 수 있는 문제입니다.
B. Ordered
문제의 description은 약간 길지만, 천천히 읽어보면 복잡한 문제는 아닙니다.
입력받은 수열이 어떤 수열인지를 판별하고, 결정된 수열에서 구해야 하는 값 (mean / frequent) 을 찾으면 됩니다.
mean의 경우는 전체를 더한 후 빈도수로 나누면 될 것이고, frequent의 경우에는 각 숫자를 count하여 제일 많이 나온
"갯수"를 세면 됩니다.
mean을 구할 때 "기약분수"로 만들어야 한다는 조건은 분자와 분모의 최대공약수를 구해서 각각 나눠주면 되겠네요.
C. ChessMetric
C번 문제부터는 알고리즘을 어느 정도 공부한 사람들을 타겟으로 맞춘 문제들이었습니다. (약간 난이도가 올라갑니다.)
시작위치에서 끝 위치까지 갈 수 있는 경우가 아주 많기 때문에 (10억 이상도 가능합니다) 모든 경우를 다 구해보는 경우
시간제한을 초과할 수 있습니다. 이 문제는 알고리즘 수업시간에 배우는 "동적 계획법(Dynamic Programming)"을 사용하면
해결할 수 있습니다.
초기에 KingKnight가 있는 위치는 (sx, sy) 입니다. 그리고 우리가 구하고 싶은 것은 "numMoves번 이동한 후 (ex, ey)에
도달하는 경로가 몇 가지나 있는가?" 입니다.
[spoiler="더 보기..."] table[i][j][k] = i번 이동한 후, (j, k) 의 위치에 올 수 있는 경우의 수
[/spoiler]
라고 정의합시다. 이 때 0번 이동한 후 갈 수 있는 곳은 (sx, sy)밖에 없고, 경우도 한 가지 밖에 없습니다. (초기 위치이기 때문에)
그러면 이제 1번 이동한 후 갈 수 있는 곳을 찾아 봅시다. table[1][A][B] 에는 table[0][A - 2][B - 1] 에서 (2, 1)만큼 이동해서 올 수도
있습니다. 또한 table[0][A][B + 1]에서 (0, -1)만큼 이동해서 올 수도 있지요. table[1][A][B]에 올 수 있는 경우는 총 16가지가 있습니
다. (그림에서 파란색으로 색칠된 부분에서 올 수 있습니다.) 다만, 보드 밖에서 뛰어 올 수는 없으니 이런 경우의 처리는 신경써 주
어야 합니다.
table을 계속 채워나가면서, table[numMoves][ex][ey] 값을 출력해 주면 됩니다.
D. Coherence
참가한 사람 중에서 제일 적은 사람이 통과한 문제입니다. 한 번에 맞은 사람도 한 명밖에 없는 까다로운 문제였습니다. :-)
(w, h) size에서 n개를 택하는 문제입니다만. (w, h) size에서 w * h - n 개를 택하는 문제와 솔루션이 같습니다. 이를 고려한 이유는
다음에 설명하는 솔루션의 "세 가지" 형태에 모든 경우를 포함시키기 위해서 입니다.
E. Tether
이 문제는 알고리즘 문제라기 보다는 어찌보면 수학문제에 가까웠습니다.
A는 염소의 위치이고, B는 사과나무의 위치입니다. |AB|는 위의 식과 같이 구할 수 있습니다.
각각의 나무에 대해 |AB| < L 인 경우가 얼마나 있는지 세 주면 됩니다.
F. HTML Validation
문제가 무려 4 Page나 되는 데다가, string 처리를 해야 하기 때문인지 코딩하는 데 시간이 꽤 필요한 문제입니다.
이런 문제의 경우에는, 입력을 잘게 쪼갠 후에, 제일 먼저 오류가 나는 태그를 찾습니다. (태그 하나에서 여러 개 나는 경우도
존재할 수 있으므로, 이 경우에는 문제에 써 있는 순서대로 체크합니다.)
문제에 써 있는 형식에는 "맞는" 데이터가 입력으로 들어오지만, "상식적이지 않은" 데이터가 들어올 수 있기 때문에,
"당연히 이런 경우는 없겠지" 라는 생각으로 코딩을 하면 말리기 딱 좋은 문제입니다. :-)
F번 문제를 제공해 주신 JM님께 다시 한 번 감사의 말씀을 드립니다. 꾸벅 _ _)/
16년 전