220903 문제 풀이 기록

오늘은 G5~G1 랜덤 디펜스를 해봤다.

원래 순서대로 푸려고 했는데, G4랑 G2 라인 문제가 잘 안떠올라서 G5-G3-G4-G1-G2 순으로 풀렸다.

 

 

총 풀이 시간: 약 2시간 20분

 

G5 | 12887 - 경로 게임

시도 횟수: 1회

체감 난이도: G5

풀이 쓸 의향: 下

풀이

단순 BFS문제. 가장 빠르게 도착했을 때 거치는 블럭 개수를 총 하얀 블럭 개수에서 빼주면 된다.

여담: 여기까지는 10분컷이었는데,,, :(

 

 

 

G3 | 19535 - ㄷㄷㄷㅈ

시도 횟수: 2회

체감 난이도: G3~G2 사이 어딘가

풀이 쓸 의향: 中

풀이

간선 개수가 3 이상인 노드에 대해서 "ㅈ" 그래프는 XC3개이고, "ㄷ" 그래프는 간선이 2개인 노드들에 인접한 다른 노드에 연결된 간선 개수 + 간선이 3개 이상인 노드들에 인접한 다른 노드에 연결된 간선 개수 * (현재 간선-1) 에 2를 나눠주자.

여담: DFS / BFS 문제인줄 알았는데 무조건 시간초과 난다는 것을 깨닫고 후다닥 풀이를 틀어버린 문제. 상당히 흥미로운 문제였다.

 

 

 

G4 | 25307 - 시루의 백화점 구경

시도 횟수: 3회

체감 난이도: G3

풀이 쓸 의향: 下

풀이

마네킹에서 BFS, 출발지점에서 BFS 돌려서 총 2회 돌리기, 근데 최적화 제대로 안하면 터짐

여담: 최적화를 제대로 안해서 한 번, 그냥 급하게 내다가 한 번 더 틀렸다. 원래 이렇게 오래 걸릴 문제는 아니었는데 마네킹에서 BFS를 돌릴 때 최적화하는 방법이 뭔가 머리에서 안떠올랐다. 피곤한 날엔 코딩하지 말아야지...

 

 

 

G1 | 21320 - 순간이동 여행

시도 횟수: 1회

체감 난이도: G1

풀이 쓸 의향: 中

풀이

어디에서 시작하든 반드시 루트 노드로 갔다가 반대쪽으로 가는 것이 최적임을 파악한 뒤, 각 트리의 높이에 따른 순간이동 최소 횟수를 dp 점화식으로 나타내어 해결하기

여담: 풀이가 꽤 재밌고 dp 점화식 구하는 과정이 흥미로웠다.

 

 

 

G2 | 1797 - 균형잡힌 줄서기

시도 횟수: 2회

체감 난이도: G2

풀이 쓸 의향: 下

풀이

남자를 -1, 여자를 1로 바꾼 뒤 부분합 처리한 뒤, i=0부터 n까지 가장 왼쪽에 있는 동일한 부분합 인덱스값 확인하면서 v[i]에서 끝나는 구간에서의 정답 구하기

여담: 처음에 prefix sum이라고 잘 생각했다가 갑자기 턱 막혀서 위의 G1 문제로 넘어갔었다.

DP로 해결되지 않을까 하는 마음에 DP 점화식을 세워보려던게 패착이었던 것 같은데, 사실 이 문제에서 prefix sum을 안쓰면 딱히 할 수 있는게 없어 보였음에도 부분합 풀이를 치워두고 DP 풀이로는 왜 갔던걸까....