본문 바로가기

전체 글

 (19)
백준 1107번 리모컨 문제 이해 이동하고 싶은 채널 번호가 주어지면 그 채널까지 이동하는 데 리모컨 버튼을 최소 몇 번 눌러야 하는지를 구하는 문제다. 리모컨 버튼은 0에서 9까지의 숫자 버튼, -버튼, +버튼이 있고, 채널은 0부터 무한대까지 있다. 숫자버튼 중 몇 개의 버튼은 고장이 나 있을수도 있다. 현재 채널은 100이다. 이동하고 싶은 채널 N이 주어지면, 고장이 나지 않은 버튼의 조합으로 N과 같거나 가장 가까운 숫자를 만든 뒤, N채널까지 -나 +버튼을 통해 이동하는 것이 최소로 버튼을 누르는 방법이다. 풀이 설명 주어진 버튼으로 N을 만들지 못하는 경우 가장 가까운 숫자를 만들어야 하는데, 어떻게 그걸 만드느냐가 문제다. 손으로 푸는 것처럼 숫자를 만들자니 고려해야 할 것들이 너무 많아 완전 탐색을 통해 해결했..
백준 1476번 날짜 계산 문제 이해 3개의 수 E, S, M으로 나타낸 연도를 우리가 알고 있는 연도로 몇 년인지 구하는 문제다. E, S, M의 범위는 각각 1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19이고, 1년이 지날 때 마다 각 수에 1을 더한다. E는 1에서 15까지의 숫자가 반복되는 것이고, S는 1에서 28까지의 숫자가, M은 1에서 19까지의 숫자가 반복되는 것이다. 예를 들어, 1 1 1년은 1년이고, 15 15 15는 15년, 1 16 16은 16년이다. 이 문제는 연도 - E = 15의 배수, 연도 - S = 28의 배수, 연도 - M = 19의 배수라는 것을 활용하면 된다. (참고) 증명 E = 1, S = 2, M = 3이고, 정답년도는 year라고 하자. E에 E의 최대범위인 15를 더하..
백준 1167번 트리의 지름 문제 이해 처음에는 트리와 그래프를 혼동했던 것 같다. 그래서 아래와 같은 상황이 발생할 수 있다고 생각하여 트리의 모든 경로를 검사하는 코드를 짰더니 시간 초과가 발생했다. 그런데 트리는 그래프와는 다르게 여러 노드가 한 노드를 가리킬 수 없다 (위키백과). 그러므로 이 문제의 경우 1. 한 노드에서부터 탐색을 하며 가장 먼 노드를 찾은 뒤, 2. 다시 그 노드부터 탐색을 하며 가장 먼 거리를 찾으면 된다. (참고) 증명 트리의 지름은 언제나 리프노드 사이에서 존재한다. 임의의 노드에서 가장 먼 리프 노드를 먼저 찾은 후, 그 리프 노드에서 가장 먼 리프노드까지의 거리가 트리의 지름이다. 아래와 같은 트리가 있다고 하자. 탐색의 시작 노드를 4번으로 했을 때, 가장 먼 리프 노드는 7번이고 거리는 11..

티스토리툴바