Sablog Models/알고리즘 13

2010 정보올림피아드 지역본선 고등부 문제 Review (3)

색상환 색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다. 그림 1. 먼셀의 20색상환 색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다. 주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자. 먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 ..

2010 정보올림피아드 지역본선 고등부 문제 Review (2)

가로수 직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다. 편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다. 예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다. 심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가..

2010 정보올림피아드 지역본선 고등부 문제 Review (1)

블로그에 떡밥이 없어서 1년이 거의 다 된 소재를 지금이라도 뿌리기로 했다. 이렇게라도 활동을 시작하면 뭔가 소재가 생각나지 않을까... (도망) 주사위 네개 1에서부터 6까지의 눈을 가진 4개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다. 규칙(1) 같은 눈이 4개가 나오면 50,000원+(같은 눈)*5,000원의 상금을 받게 된다. 규칙(2) 같은 눈이 3개만 나오면 10,000원+(3개가 나온 눈)*1,000원의 상금을 받게 된다. 규칙(3) 같은 눈이 2개씩 두 쌍이 나오는 경우에는 2,000원+(2개가 나온 눈)*500원+(또 다른 2개가 나온 눈)*500원의 상금을 받게 된다. 규칙(4) 같은 눈이 2개만 나오는 경우에는 1,000원+(같은 눈)*100원의 상금을 받게 ..

2009 정보올림피아드 지역본선 문제 Review (5)

시험 당일에 5개의 문제 중 5번을 가장 쉽게 푼 것 같다. 중앙문자열 문자열에서 교체 연산은 문자열의 한 문자를 다른 문자로 바꾸는 연산이다. 예를 들어, 문자열 “computer”에서 4번째 문자 p를 m으로 교체하면 “commuter”가 된다. 같은 길이의 두 문자열 P와 Q의 거리 d(P,Q)는 P를 Q로 바꾸기 위한 교체 연산의 최소 개수로 정의된다. 예를 들어 P = “computers”, Q = “consumers”라 하면, P에서 3번째 문자 m을 n으로, 4번째 문자 p를 s로, 6번째 문자 t를 m으로 바꾸면 Q가 된다. 따라서 P와 Q 사이의 거리는 3이다. A, B, C를 같은 길이의 문자열이라 하자. 이 때 어떤 문자열 W의 반경 r(W)는 문자열 W와 문자열 A, B, C와의 거..

2009 정보올림피아드 지역본선 문제 Review (4)

복불복 1박2일 제작진은 다음과 같은 새로운 복불복 게임을 제안하였다. 먼저 게임을 하는 한 사람에게 K개의 조약돌을 주고, 숫자가 적혀있는 회전판을 N번 돌리게 한다. 게임을 하는 사람은 회전판을 돌려서 나오는 숫자만큼의 조약돌을 제작진에게 되돌려 주어야 한다. 회전판을 N번 돌리는 동안 제작진에게 줄 수 있는 조약돌이 있으면 게임을 하는 사람이 이기게 되고, 제작진에게 주어야 하는 조약돌이 모자라게 되면 게임에서 지게 된다. 회전판에는 T개의 숫자가 그려지고, 그려지는 숫자는 0 이상 T-1 이하의 정수 중 하나이다. 회전판에 사용되는 정수는 중복 사용이 가능하고, 0부터 T-1 사이의 정수 모두가 다 회전판에 나타나야 하는 것은 아니다. N과 K, 그리고 T와 회전판에 그려진 모든 숫자가 주어질 때..

2009 정보올림피아드 지역본선 문제 Review (3)-3

이 포스트에서는 지난번에 올린 소스 코드가 어떤 식으로 구성되었는지 설명해 보겠다. (참 빨리 올린다...=_=;) 사실 문제를 풀 만한 사람이라면 설명할 필요조차 없는 문제와 코드였다. 문제의 단서는 여기에 있다. 주어진 논을 N × N 행렬로 볼 때 형이 특정 열에서 할당받는 구역의 개수는 바로 왼쪽 열에서 받은 구역의 개수보다 크거나 같아야 한다.문제에서는 이것이 제약조건처럼 나왔다. 하지만 만약 이 조건이 없다면 최적의 조건을 찾기 위해서는, 프로그램은 위-아래로 나누는 모든 경우를 읽어야 한다. 만약 그렇다면 1열을 1개, 2개, …, n개까지 나누는 각각에 대해 2열을 1개, 2개, …, n개까지 나누고, 그런 작업을 n열에 이르기까지 했어야 한다. 각 열마다 동생에게 할당되는 칸(위에서부터 ..

2009 정보올림피아드 지역본선 문제 Review (3)-2

지난번에 문제를 3번까지 올리다 만 사실조차 까먹고 말았다가 이제 깨달았다. 알고 보니 내 컴퓨터에도 문제를 풀어 놓은 소스가 없었다. (난 뭐-_-지 ㅜㅠ) 시험기간 중간에 낀 주말이지만, 무시하고 지나가기에는 너무 큰 문제라서 손을 대기로 했다. 그리고 코딩 따위를 금방 끝냈다. #include #include #include char table[20][20]; char solution[20], solving[20]; int total = 0; int size; int diff_now, diff_best; void tablein(); void divide(char col); void checknow(); void makesol(); int uppersum(); void finish(); int mai..

2009 정보올림피아드 지역본선 문제 Review (3)-1

3번 문제는 처음 보고 정체를 알 수 없었다. 의좋은 형제 어떤 N × N 개의 단위 구역으로 구성된 논이 있다. 각 단위 구역에서는 쌀이 생산되는데 구역에 따라서 쌀의 생산량이 다르다. 아래는 5 × 5 = 25개의 단위 구역으로 나누어진 논을 보여주고 있다. 각 구역에 적혀 있는 숫자는 예상되는 쌀의 수확량(가마)이다. 3 4 5 1 8 8 2 3 2 2 0 2 9 5 4 1 11 3 0 5 4 5 2 7 1 두 의좋은 형제는 이 N × N의 논을 다음과 같이 두 부분으로 나누어 형은 아래쪽에 있는 땅을 가지고, 동생은 위쪽의 땅을 가지기로 하였다. 전체 구역을 마구잡이로 나누면 기계로 농사를 짓는데 불편하기 때문에 각 형제에게 배분된 구역이 단조 증가하는 계단 모양이 되게 하려고 한다. 즉, 주어진..

2009 정보올림피아드 지역본선 문제 Review (2)-3

이번 솔루션은 다소 간단하다. 또한 내가 작년에 쓰다가 한 문제를 망치게 만든 바로 그 방법이기도 하다.... (당시 int 형 변수를 제곱한 만큼 신규 할당시켰더니 오버플로) 바뀐 줄은 강조해 놓았다. #include #include int main() { int n, i, j; int higher = 0; int *tower = (int *)malloc(sizeof(int)*500001); FILE *fpi, *fpo; tower[0] = 100000000; fpi = fopen("INPUT.TXT", "r"); fpo = fopen("OUTPUT.TXT", "w"); fscanf(fpi, "%d", &n); for (i = 0; i < n; i++) { fscanf(fpi, "%d", tower +..

2009 정보올림피아드 지역본선 문제 Review (2)-2

일단 첫 번째 해법. 새로 입력받아서 비교한다! 어차피 입력받으면서 비교한 결과 출력하고 있으니까. #include int main() { int n, i, j; int tower, comp; int higher; FILE *fpi, *fpc, *fpo; fpi = fopen("INPUT.TXT", "r"); fpo = fopen("OUTPUT.TXT", "w"); fscanf(fpi, "%d", &n); for (i = 0; i < n; i++) { higher = 0; fscanf(fpi, "%d", &tower); fpc = fopen("INPUT.TXT", "r"); for (j = 0; j < i; j++) { fscanf(fpc, "%d", &comp); if (comp >= tower) hi..