Skip to content

BOJ 17838-17845 제1회 UNIST 알고리즘 프로그래밍 경시대회 Uni-CODE

https://www.acmicpc.net/category/detail/2105

BOJ 17838 커맨드

문자열의 길이가 7인지 봅니다. 그 다음,

(1) 1, 2, 5번째 글자가 같고,

(2) 3, 4, 6, 7번째 글자가 같고,

(3) 1, 3번째 글자가 다른지 보면 됩니다.

BOJ 17839 Baba Is Rabbit

전형적인 그래프 탐색 문제입니다. 단, 정점이 정수가 아니라 문자열로 표현되므로, [[맵]] 등을 통해 문자열을 정수로 매핑해 준 다음, 그것으로 그래프를 건설해야 합니다.

BOJ 17840 피보나치 음악

피보나치 수를 M으로 나눈 나머지는 주기 수열입니다. 즉 "i번째 피보나치 수를 M으로 나눈 나머지"를 f(i)라고 할 때, 어떤 양의 정수 k가 존재하여, 모든 n에 대해 f(i+k) = f(i)입니다.

비둘기집의 원리를 쓰면 간단하게 증명될 것처럼 생겼지만, 사실 비둘기집의 원리로는 "적당한 i가 존재하여 f(i), f(i+1), ...이 주기 수열이다"만 증명할 수 있습니다. 진짜 증명은 아래 페이지를 참조하세요.

피보나치 수열 mod M의 주기

수열의 주기를 찾으려면, 수열을 만들면서 마지막 두 항이 (1, 1)이 될 때 멈추면 됩니다. 이제 각 수에 적힌 숫자들을 다 분해하면 건반을 누르는 순서가 나옵니다. 이 순서의 길이를 K라고 할 때, (N-1)%K번째 인덱스에 있는 수를 출력하면 됩니다.

BOJ 17841 UNIST는 무엇의 약자일까?

DP[i][j] = "첫 i개의 단어를 사용하면서, UNIST의 첫 j글자를 만드는 경우의 수"로 정의합니다. 다이나믹 프로그래밍입니다. i번째 단어의 접두사가 UNIST의 L번째부터 R번째까지와 같으면, DP[i][R]에 DP[i-1][L-1]을 더합니다.

BOJ 17842 버스 노선

리프 노드의 개수를 L이라고 합시다. 하나의 노선은 최대 두 개의 리프를 덮을 수 있으므로, 최소 ceil(L/2)개의 노선이 필요합니다. 흥미롭게도 ceil(L/2)개의 노선으로 항상 트리 전체를 덮을 수 있기 때문에, 답은 ceil(L/2)입니다.

증명은 정점 개수에 대한 귀납법으로 할 수 있습니다. 정점이 2개 이하일 때는 자명합니다. 정점이 k개 이하일 때 (k>=2) 성립한다고 가정하고, k+1개일 때를 봅시다. 두 가지 경우가 있습니다.

  1. 리프 노드 중에, 지웠을 때 리프 노드의 개수가 유지되는 노드가 존재하는 경우. 그 리프 노드를 x로 표기하고, x에 인접한 유일한 정점을 y라고 합시다. x를 지우면 나머지 트리는 귀납법에 의해 ceil(L/2)개의 노선으로 덮을 수 있습니다. y가 새로운 트리의 리프이므로, y를 끝점으로 갖는 노선이 존재합니다. x를 다시 추가하고, 그 노선을 x로 확장하면 됩니다.
  2. 그런 리프 노드가 없는 경우. 정점이 3개 이상인 트리에는 차수가 2 이상인 정점이 반드시 존재합니다. 그 정점 R을 루트로 잡으면, R의 자식에 따라 두 개 이상의 서브트리가 생깁니다. 그 중 두 서브트리를 잡으면, 각각은 리프 노드를 가지고 있습니다. x와 y라고 합시다. x, y를 지우면 리프 노드의 개수는 2 줄어들고, 귀납법에 의해 ceil(L/2)-1개의 노선으로 나머지 트리를 덮을 수 있습니다. 이제 x와 y를 다시 추가하고, x에서 y로 가는 노선을 놓으면 됩니다. 

BOJ 17843 시계

12시 방향의 각도를 0이라고 할 때, 시침의 각도는 12h + m/5 + s/120, 분침의 각도는 6m + s/10, 초침의 각도는 6s입니다.

각도가 A와 B인 두 반직선 사이의 각도를 구하려면, 먼저 시계 방향 거리 CW = abs(A-B)를 구하고, 반시계 방향 거리 CCW = 360-CW를 구합니다. 그러면 각도는 min(CW, CCW)입니다.

BOJ 17844 복붙하기

길이가 L인 문자열이 겹치지 않게 두 번 등장하는지 판별할 수 있으면, 이분 탐색으로 최대의 L을 찾을 수 있습니다.

저는 [[접미사 배열]]을 사용했습니다. 부분문자열 [i ... i+L-1]과 [j ... j+L-1]이 같을 필요충분조건은 이렇게 결정할 수 있습니다.

  1. 접미사 배열에서 i와 j가 등장하는 위치를 찾습니다. 두 위치 중 작은 쪽을 x1, 큰 쪽을 x2라고 합시다.
  2. 그러면 LCP 배열의 x1+1, x1+2, ..., x2번째 원소는 전부 L 이상이어야 합니다.

따라서, LCP 배열에서 x1+1, ..., x2번째 원소가 전부 L 이상이라면, 접미사 배열의 x1, ..., x2번째 원소 i 중 어느 것을 고르더라도, 부분문자열 [i ... i+L-1]은 항상 같습니다. 그러므로 x1, ..., x2번째 원소 중 최댓값과 최솟값의 차이가 L 이상이면 그 부분문자열 [i ... i+L-1]은 겹치지 않게 두 번 등장합니다.

LCP 값이 L 이상인 모든 연속한 구간에 대해 이 과정을 적용해 주면 됩니다.

BOJ 17845 수강 과목

전형적인 [[배낭 문제]]입니다. DP[i][j] = "첫 i과목 중에서 선택, j시간 만큼 공부했을 때 중요도의 합"으로 둡니다.