A - 15894번: 수학은 체육과목 입니다
둘레를 잘 펼쳐서 세어보게 되면 4*N이 나온다.
이 때 N이 최대 10^9이므로 long long타입으로 변환하여 출력 해주면 풀 수 있는 문제이다.
G - 15904번: UCPC는 무엇의 약자일까?
문자열을 getline함수를 이용하여 한 줄씩 입력 받은 뒤
문자열을 앞에서부터 U, C, P, C가 나오는 지 확인 해주면 풀 수 있는 문제이다.
B - 15903번: 카드 합체 놀이
1715번: 카드 정렬하기 문제와 매우 유사하다. 탐욕법 기법을 사용하는 문제이다.
가장 작은 수가 쓰여진 두 개의 카드를 합치는 것이 합체를 했을 때 작은 숫자가 나오는 가장 좋은 방법이므로
M번 만큼 반복적으로 가장 작은 수가 쓰여진 두 카드를 찾은 뒤 합쳐서 다시 그 카드들도 정렬해주며 진행해주면 되는 문제이다.
최소 힙(우선순위 큐)를 사용하여 매번 다시 정렬하지 않고 좀 더 빠른 시간에 그 때의 두 카드를 고를 수 있다.
수가 최대로 합쳐질 경우 int범위를 벗어날 수도 있으므로 long long타입을 사용하면 풀 수 있는 문제이다.
D - 15900번: 나무 탈출
리프 노드에 있는 말을 루트 노드로 매 턴마다 한 칸씩 이동한다.
이는 루트 노드부터 리프 노드까지 거리 만큼이 들며 모든 리프 노드에서 루트 노드까지의 거리,
즉 리프 노드의 깊이를 모두 더해준 뒤 이 값이 홀수인지 짝수인지에 따라 답을 출력해주면 되는 문제이다.
H - 15897번: 잘못 구현한 에라토스테네스의 체
12의 경우
1 -> 12
2 -> 6
3 -> 4
4 -> 3
5 -> 3
6 -> 2
7 -> 2
8 -> 2
9 -> 2
10 -> 2
11 -> 2
12 -> 1
를 모두 더해 41이라는 값이 나오게 된다. 우항은 모두 N/i를 올림한 값, 즉 ceil(N/i)이 되며 이들을 모두 더해주면 된다.
그러나 N이 최대 10^9이기에 모든 값을 하나하나 구할 수는 없으므로 이를 처음에는 값이 급격하게 변하다가
어느 순간부터는 같은 값이 반복되는 것을 알 수 있는데 이를 이용하여 sqrt(N)만큼은 ceil(N/i)값을 구하여 더해 준 뒤
이후는 다음 숫자가 나올 수 있는 범위 (위 예제에서 2가 나올 수 있는 범위는 12/2 부터 12/1-1이 된다.)를 한번에 계산하여
시간 복잡도를 줄일 수 있다.
F - 15899번: 트리와 색깔
f(v, c) : 정점 v가 루트인 부트리(sub-tree)에서 색깔이 c 이하인 정점의 개수를 묻는 질의를 2*10^5개를 해결해야하는데
매번 질의마다 DFS를 해서 구하기에는 시간복잡도가 O(N^2)으로 시간 내에 풀 수 없다.
먼저 부트리를 효율적으로 계산하기 위하여 트리를 DFS순서로 다시 번호를 매기면서 in, out배열을 생성하여
v정점이 루트인 부트리의 번호 범위를 in[v]~out[v]로 표현한다.
이 때 질의의 답은 v정점의 부트리 범위에 해당하는 노드 중 색이 c이하인 정점의 개수이므로
구간 합을 구하는 구간트리를 이용하여 색깔을 작은 순으로 부터 구간트리에 업데이트한 뒤 범위의 값의 합을 이용해주면
답을 구할 수 있다.
I - 15898번: 피아의 아틀리에 ~신비한 대회의 연금술사~
완전탐색 기법을 사용하여도 시간내에 돌아가는 문제이다.
최대 10개의 재료 중에 3개의 순서를 선택하고 (10*9*8 = 720)
선택한 재료들은 4종류의 회전이 가능하며 (4 * 4 * 4 = 64)
각 재료들의 시작점은 (1, 1), (1, 2), (2, 1), (2, 2)가 가능하며 (4 * 4 * 4 = 64)
이들을 5*5 칸의 4*4만큼에 3번 담아야하므로 (4 * 4 * 3= 48)
여러 중첩 포문을 이용하여 계산하면 풀 수 있는 문제이다.
(정해는 9중포문을 이용하였지만 나는 13중 포문이 나왔다.)
C - 15902번: Split and Merge
개수를 구하는 것은 어렵지 않다. 현재 나뉘어져 있던 세로선이 없어졌거나 다시 생겼을 경우
이들의 개수를 세어서 몇 번 연산을 해야 하는 지 계산할 수 있다.
이후 경우의 수는 DP를 이용하여 구하는 데 이는 정해를 참고하였다.
각 나눠진 부분의 경우의 수를 각각 계산한 뒤 한 번에 계산하기 위해 부분문제로 나누게 되면
나눠진 것을 1, 안나눠진 것을 0으로 봤을 때 01010...이라는 값을 10101...로 0이 연속하지 않게 변환하는 수와 같다.
이는 0 -> 1로 먼저 변환하는데 이렇게 변환 할 시, 그 1을 기준으로 앞과 뒤에 똑같은 패턴이 나타난다.
점화식 D[i]을 i자리의 010101..값을 101010..으로 변환시키는 데의 경우의 수라 했을 때
D[i] = D[0]*D[N-1]*N-1C0 + D[2]*D[N-3]*N-1C2 ... 로 진행이 된다.
각 항의 뒤에 붙은 조합은 지금 0을 1로 변환한 1개를 제외하고 나머지들은 N-1번 변환하여야 하는데
왼쪽으로 나눠진 구간을 x, 오른쪽으로 나눠진 구간을 N-1-x라 하면 이들의 순서를 정하는 방법은 N-1Cx가 되기 때문이다.
이렇게 구한 뒤 각 나눠진 부분의 길이를 각각 L1, L2, ,,, Lk라 하였을 때
D[L1] * .... * D[Lk]를 모두 곱한 뒤 고르는 순서의 경우의 수도 고려해주어야 하므로
(L1 + L2 + L3 ... + Lk)! / (L1! L2! L3! ... Lk!)을 추가적으로 곱하여 준다.
이 때 수가 매우 크기에 나머지 연산을 사용하는 데 나누기를 할 때에는 정수론에서 사용한 페르마의 소정리를 이용하여
나머지 연산의 곱셈 역원을 구하여 곱하여 계산하였다.
E - 15901번: 소각로
X
J - 15896번: &+ +&
X
