20230126

1. 백준 1149 RGB거리

맨 처음 집을 Min()으로 최소값을 구한 후, 풀어보려다가

26	40	83
01	60	57
30	02	50

이런 경우에는 맨 처음 집을 무조건 최소값을 고르는게 아니라는 것을 발견했다. DP로 풀면 될 것 같다는 생각이 들었고, 고정 값이 어디일까를 고민해보았다. n이 최소 2이고 문제에서도 i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 라고 되어있으니 구할 수 있는 정확한 값은 가장 첫번째 값이 아니라 두번째 값 부터겠구나 싶었다.

비용을 입력해둔 배열을 재활용 해서 각각의 집에 대해

• 이전 집의 빨, 초, 파 값과 다음 집의 빨, 초, 파 값 중 작은 것을 찾고
• 자기 자신의 빨, 초, 파 비용을 더해나가는 식으로 구현
• 마지막 집 기준으로 빨, 초, 파 어느 비용이 가장 적은지 찾으면 끝

DP 배열을 따로 안만들고 입력 받은 원본을 수정해서 쓰는 경우도 있다는 것을 배웠다.

 

2. 백준 7576 토마토

처음에 그냥 토마토가 다 익었는지 아닌지 판단하는 문제로 착각하고 dfs로 풀었다가 최소 비용을 구해야 하는걸 깨닫고 bfs로 다시 풀었다.

bfs로 구현하기 시작하면서도 실수를 했는데, 최단거리 구할 때 근접 노드로 이동하며 이전 노드에 +1 해주는 식으로 하면 편한걸 count 변수를 두고 뭔가.. 뭔가를 세려고 했다….

간단한 문제인거 같은데... count 구현이 잘 안되고 어렵게 느껴져서 '아 이게 아닌거같은데' 하다가 근접 노드에 +1 씩 해주며 bfs를 진행하는 방식의 풀이가 떠올랐다.

최소 시간, 최단 거리 구할 때는 bfs, 다익스트라, 플로이드워셜을 떠올리고 상황에 맞게 사용하자.. !!!!! bfs는 비용이 1일 때 우선적으로 떠올릴 것!