2025-03-13 PS

매직스퀘어 (S5, K512)

그냥 조건에 맞는대로 짜면 된다. 주의해야 할 점은 구현할 때 숫자가 겹치는지 확인 할 때 배열 크기가 충분한지를 잘 확인해야한다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/15739.cpp

스케이트 연습 (S4)

속도는 마음대로 올릴 수 있으나 마음대로 내릴수는 없고 처음과 끝 모두 속도가 0이어야 하므로 끝점서부터 시작하여 각 지점에서 낼 수 있는 최대 속도를 구해준다. 

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/28324.cpp

 

대피소 (S4)

N이 매우 적으므로  K=1, 2, 3에 따라 그냥 모든 경우의 수를 다 돌아보면 된다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/28215.cpp

 

영어 시험 (S4, K512)

알파벳 종류가 n개일때 길이가 n인 문자열을 모두 뽑아내려면 최소 n^2개 필요하면서 모든 알파벳이 n개씩 있어야 한다. 이를 이용하면, n칸 간격으로 주어진 모든 알파벳을 쓰면 항상 길이가 n인 문자열을 모두 뽑아낼 수 있다. 주어진 문자열이 길이가 n이면서 주어진 모든 종류의 문자열을 가지고 있으므로 이를 n번 출력해주면 답이다. 

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/25288.cpp

 

호숫가의 개미굴 (G5)

약점문제인듯. 

dp(i,j,k) = i번째 개미굴의 상태가 j (개미가 있으면 1 아니면 0)이고 1번 방 상태가 k(개미가 있으면 1 아니면 0)일때 최적해

이를 이용해서 n번째 방 상태가 비어있는가에 따른 케이스들을 다 비교해서 답을 구하면 된다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/28325.cpp

 

카드 바꾸기 (G5)

N<=500이므로 랜덤한 두 지점을 잡고 등차수열을 만든다음 원본이랑 비교해가면서 최적해를 구하면 된다. 시간복잡도는 O(N^3)이라서 충분히 통과한다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/25401.cpp

휴먼 파이프라인 (G5, K512)

일 잘하는 사람들과 못하는 사람들을 갈라서 팀을 만드는데, 이때 각 팀의 속도를 x, y라고 하고, 일한 시간을 t라고 하자. 그러면 t*(x+y)>=k 이므로, t>=k/(x+y)이다. 그러므로 t의 최솟값은 ceil(k/(x+y))이다. 이때 잘하는 팀과 못하는 팀의 경계를 임의로 두면서 ceil(k/(x+y))의 최솟값을 구하면 된다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/22981.cpp

 

트리 뽑아내기 (P4)

규칙대로 하면, 기존에 있던 루트 노드가 사라지고 나머지 경로에 있던 것들이 위로 올라오는 느낌이다. 그렇다면, 루트노드가 없어질 때 다음 루트노드는 무엇이 되는지 생각하면, 결국엔 자식 노드들 중에서 가장 가중치가 낮은 노드가 루트 노드가 된다. 이를 이용해서 우선순위 큐로 루트를 pop하고 그의 자식들은 in해주는 방식으로 하면 된다. 이게 되는 이유는 우선순위 큐에 있는 노드가 당장에 루트의 자식 노드가 아닐지라도 게속 해서 노드들이 빠져나가서 헤당 노드가 나갈 타이밍이 되면, 이미 루트의 자식노드가 되어있는 꼴이기 때문이다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/32072.cpp

 

이진 트리 (P4)

Tree DP.

 

C_i : 트리 T_i의 리프노드 갯수

Ldp_i : 트리 T_i에서 ∑f(k, C_i) (k=1...C_i)

Rdp_i : 트리 T_i에서 ∑f(1, k) (k=1...C_i)

dp_i : 트리 T_i에서 ∑f(j, k) ( j=1...C_i, k=1...C_i, j<=k)

 

로 정의하고 식을 세우면, 

Ldp_0 = Rdp_0 = dp_0 = 1

dp_i = dp_(A_i) + dp_(B_i) + Ldp_ (A_i)*C _(B_i) + Rdp_ (B_i)*C _(A_i) - 1

Ldp_i = Ldp _(A_i) + Ldp _(B_i) + C _(A_i) - 1

Rdp_i = Ldp _(A_i) + Rdp _(B_i) + C _(B_i) - 1

이다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/31966.cpp

 

White Magic (CF 2066B, 1900, Upsolving)

관찰하면 0이 없을때 mex는 항상 0이므로 0을 최대한 제외하는것이 좋고 0이 두 개 이상 있으면 조건을 성립하지 않는 경우가 무조건 존재한다. 이유는 i를 기점으로 해서 a_k = 0, a_l = 0, (0<k<=i<=l<=n, k<l)인 k, l이 존재하면, 조건을 참고했을 때 min값이 0, mex값이 1이 되므로 조건을 성립하지 않는 경우가 무조건 생긴다. 그러므로 0은 최대 하나만 있을 수 있다.

이때 0이 되는지 안되는지는 그냥 직접 확인해주면 된다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Codeforces/Codeforces%20Round%201004%20(Div.%202)/E.cpp