TIL 2022-06-09-목

1. 학습한 내용

백준 동적프로그래밍 1149번 문제, DFS 24479번 문제

• 1149번 풀이(반복문)
• 1149번 풀이(재귀)

• 24479번 풀이

2. 알게 된 내용

1149번 문제

점화식을 세우는 게 어려워서 다른 분의 설명을 참고하고 이해하면서 풀었다.
모든 경로의 경우의 수를 다 구하면서 최종적으로 작은 누적합을 찾는 것이 키포인트라고 한다.
각 집/색깔마다 비용 값의 누적합(같은 색깔이 아닌 것들만 더하면서)을 다 구하면서 마지막 집까지 다 구하고, 마지막 집 비용의 최솟값을 찾으면 되는 것이다.

아래 출처 글에서 올려주신 그림인데, 이 그림을 보고 잘 이해가 되었다.

출처 : https://st-lab.tistory.com/128

22479번 문제

나는 DFS가 어려워서 관련 문제들을 찾아서 한번 내 힘으로 풀어보려고 했다. 나는 인접행렬이 더 효율적일 것이라 생각해서 인접행렬로 풀어보았는데 채점해보니 메모리 초과가 떴다. 인접리스트는 더 많은 메모리를 차지할 것이라 생각했는데, 다른 분의 풀이를 찾아보니 인접리스트로 간선을 표현하고 미리 오름차순으로 각 정점의 간선들을 정렬시켜두면 더 효율적이라고 한다.

출처 : https://nahwasa.com/entry/%EC%9E%90%EB%B0%94-%EB%B0%B1%EC%A4%80-24479-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-1-boj-java