1월 12일 PS 일기

어제 몸살기운이 심해서 PS를 하나도 안 했다.

오늘 낮까지도 침대에 누워만 있다가 저녁먹고 백준에서 3문제 업솔빙했다.

 

22933번. TraveLog

1월 9일날 셋돌다가 풀이는 바로 나왔는데 구현을 못해서 던진 문제였다.

코드 엎고 다시짜니까 (TLE 2번받고) 맞았다.

풀이

다익스트라를 돌려서 1번 정점부터 다른 정점들로의 최단경로를 구한다. 이 최단경로에 속하는 간선 (a -> b)중, dist[a] 초과 dist[b] 미만인 TraveLog의 기록이 존재하지 않는 간선들만 따로 저장한다. 이 간선들로 다익스트라를 한번 더 돌려서 n까지 가는 경우의 수를 세고, 경우의 수가 1인 경우에만 DFS를 돌려서 경로를 찾아줬다.

이렇게 했는데 시간초과가 나서 DFS를 돌리는 중에 경우의 수가 2 이상인 정점을 만나면 바로 return한다고 수정했더니 맞았다.

실제 난이도 P4, 체감 P4~P3

33031번. Expression Correction

1월 2일날 셋돌다가 터진 문제였다. 풀이는 자명한데 계속 WA를 받아서 에디토리얼을 깠더니 문제를 잘못 읽어서 틀린거였다.

풀이

가능한 모든 경우에 대해서 올바른 등식인지 판별하면 된다. 근데 고려할 점이 많아서 실수하기 아주 쉽다.

1. Leading zero가 있으면 안 된다. << 예제 3에서 걸러진다.

2. 11개 연속으로 숫자가 있으면 안 된다. << 예제 5에서 걸러진다.

3. 등호 여러 개 있는 경우도 고려해야 한다. << 이건 그럴수도 있고 아닐수도 있음. 근데 난 혹시 몰라서 구현했다.

이거 말고도 고려할게 많은데 에디토리얼에 잘 나와 있다.

실제 난이도 G5, 체감 P5이상

27604번. Vittorio Plays with LEGO Bricks

1월 3일날 셋돌다가 구현을 못해서 터진 문제였다. 셋 끝나고 flappybird(aka asdfsdf)와 이야기해 봤는데 구현이 내 생각보다 간단해서 금방 구현했다. 오늘 푼 세 문제중에 가장 빨리 풀었다.

풀이

"파일 합치기" 식 DP를 하면 된다. i~j 구간을 합칠 때 맨 아랫블록의 높이가 고정되어 있다는 점을 이용하면 dp 배열을 쉽게 만들 수 있다.

실제 난이도 P4, 체감 P5

오늘 푼 문제들은 다 풀이는 알지만 구현에서 말려서 못 푼 문제들인데, 내일부터는 풀이를 모르는 문제들을 업솔빙해야 한다. 내일부터 포스텍으로 특강들으러 가는데, 그 때 틈틈이 업솔빙 열심히 해야겠다