PS 1000문제 도전기 - 1일차 [백준]

오늘 공부한 내용 & 푼 주요 문제

9657 - 돌 게임 3(실버 3)

https://www.acmicpc.net/problem/9657

9659 - 돌 게임 5(실버 3)

https://www.acmicpc.net/problem/9659

9660 - 돌 게임 6(골드 5)

https://www.acmicpc.net/problem/9660

9661 - 돌 게임 7(골드 2)

돌 게임 시리즈를 풀어봤다. 전반적으로 dp에 대한 기본적인 이해를 요구했고, 9660,9661은 이를 토대로 일반항을 세워 O(1)의 시간복잡도를 요구하는 문제였다. 돌 게임 시리즈의 마지막 문제인 돌 게임 8은 이를 더 일반화 하는 내용인데, 이에 대한건 조금 더 공부를 하고 풀어봐야겠다.

 

1439 - 뒤집기(실버 5)

https://www.acmicpc.net/problem/1439

간단히 1과 0이 바뀔때 카운트를 해주어 최솟값을 뽑아내면 되는 문제.

 

2096 - 내려가기(골드 5)

https://www.acmicpc.net/problem/2096

dp를 이용하여 푸는 문제다. n번째 줄에서 n-1번재 줄까지의 합 중 최댓값(혹은 최솟값)을 계속해서 더해주어 최댓값,최솟값을 구해주는 문제이다. 비슷한 문제로는 RGB 거리(1149)가 있다.

 

11725 - 트리의 부모 찾기(실버 2)

https://www.acmicpc.net/problem/11725

트리가 주어졌을때 부모를 찾아내는 문제다. 1을 루트로 삼는다고 했으니 1부터 시작하여 bfs를 이용해 노드에 번호를 매겨주고, 각 노드마다 연결된 노드중 최댓값을 가지는 노드를 출력해주면 된다.

 

17070 - 파이프 옮기기(골드 5)

https://www.acmicpc.net/problem/17070

bfs를 사용해서 푸는 문제... 인 줄 알았으나, 시간 초과가 나서 dfs로 푼 문제이다.(이에 대해서는 좀더 공부 후 나중에 문제풀이 글에서 설명해보겠다) dfs를 돌릴때 x,y와 방향(r)을 같이 리스트에 넣어 케이스를 나눠 탐색해주었다.

 

오늘 푼 잔여 문제

 

18문제 풀었다.

현황

레이팅: 1048 -> 1088(+48)

푼 문제 수:406 ->431(+25)