평범한 회사 일기

과제 4: 레드-블랙 하노이탑 하노이탑은 모두가 잘 알고 있는 문제이다. a, b, c 3개의 원기둥이 있고, 서로 다른 크기의 n개의 구멍뚫린 원반이 a에 크기 순으로 놓여 있는데 이를 c로 다음 규칙을 지키면서 이동하면 된다. - 한번에 한개씩 - 작은 원반 위에 큰 원반 x 이제 2n개의 구멍뚫린 원반을 이용하는 하노이탑을 생각해보자. 원반의 크기는 n가지로, 각 크기마다 빨간 원반, 까만 원반 둘이 있다. 처음 a기둥에는 원반이 크기순서대로 놓여 있는 것은 같지만, 같은 크기의 원반 둘은 빨간 원반이 까만 원반 위에 있다. 이제 하노이탑 규칙을 따르면서, c 기둥에 그대로 원반을 모두 옮기려고 한다. (크기 순서대로, 같은 크기는 빨간 원반이 까만 원반 위) 이 때 필요한 원반의 최소 이동회수를 ..

과제 3: 동전 모으기 N x M 크기의 네모칸들이 있다. 각 칸에는 0개 이상 100개 이하의 동전이 있다. 이제 가장 왼쪽 위 네모칸에서, 가장 오른쪽 아래 네모칸으로 이동하려고 한다. 이동할 때는 바로 오른쪽 옆 네모칸, 또는 바로 아래 네모칸으로만 이동할 수 있다. 예를 들어 아래와 같이 4 x 5 크기 네모칸을 생각해보자. 숫자는 각 칸에 있는 동전의 개수이다. 0 4 0 2 0 1 2 0 0 1 1 0 3 0 0 2 1 2 4 2 가장 왼쪽 위에 있는 0개의 동전이 있는 칸에서, 가장 오른쪽 아래에 있는 2번 동전이 있는 칸으로 위 규칙을 지키면서 이동하려 한다. 예를 들어, 0 - 4 - 2 - 0 - 3 - 2 - 4 - 2로 이동하면 총 17개의 동전을 얻을 수 있다. 이 과정에서 얻을 ..

과제 2: 파란 점 하얀 점 2차원 좌표평면 (0, 0) 부터 (N, N) 안에 M개의 하얀 점이 있다. 점의 X, Y 좌표는 0 이상 N 이하인 정수임에 유의하라. 이 점 중 일부의 점을 파란 색으로 바꾸어 칠하려고 한다. 파란 점들을 이은 다각형을 만들었을 때, 이 다각형의 바깥에 하얀 점이 없게 하려고 하고, 또한 가장 적은 개수의 하얀 점을 파란 색으로 바꾸어 칠하려고 한다. 또한, 셋 이상의 점이 한 직선 위에 있는 경우는 없다. 좌표 평면의 크기 N, 하얀 점의 수 M이 주어졌을 때, 위 조건을 만족하는 파란 점의 개수를 출력하는 프로그램을 작성하시오. 입력 표준 입력으로 입력을 받는다. 첫 줄에는 좌표 평면의 크기 N, 하얀 점의 수 M이 주어진다. N은 unsigned int로 표현 가능한..

어렵지 않게, (4, 4)부터 (4, 4)까지의 합을 구하면 1이다. 입력 표준입력으로 입력이 주어진다. 첫 줄에는 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. N은 1 이상 1024 이하, M은 1 이상 100,000 이하이다. 그 다음 N 줄에는 표에 대한 정보가 주어진다. 한 줄에는 N개의 숫자가 사이에 공백을 두고 주어진다. 이 수들은 모두 1 이상 1,000 이하인 정수이다. 그 다음 M개의 줄에는 각각의 줄마다 a b c d 4개의 정수가 주어지는데, 이들은 모두 1 이상 N 이하이며, a는 c 이하, b는 d 이하이다. 이는 (a, b)부터 (c, d)까지의 직사각형 부분에 대한 합을 구하라는 것이다. 출력 입력에서 각 줄에 주어진 a b c d마다 해당하는 합을 한 줄에 출력한다..