백준 문자열지옥에빠진호석 JAVA (1) 썸네일형 리스트형 [백준] 문자열 지옥에 빠진 호석 20166 [JAVA] | Link www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net | 풀이 DP를 처음 적용해본 문제이다. ㅎㅎ c->a->b의 개수를 구할 때, 색칠한 a로 부터 갈 수 있는 b의 길은 2가지로 정해져있다. 따라서, a에서 또 dfs 를 통해 탐색할 필요가 없다는 것을 깨달았다. ==> a로부터의 가짓수가 많아지면 낭비 심해짐 그러므로 DP를 적용하기로 생각했다. 어떻게 적용할 수 있을까? 문자열의 끝부분 부터 탐색하며, 문자열의 첫 부분에는 해당 값들을 모두 더해주면 된다. DP를 3차원 배열로 만들어서 신이 좋아하는 문자열의 맨 끝부분 부터 .. 이전 1 다음
