백준 1103번 게임 - C++(cpp) 풀이
1. 그래프에 사이클이 존재하면 무한번 움직일 수 있다. DFS를 이용해 사이클을 확인한다. 2. dp(r, c) = (r, c) 위치에서 시작했을 때 최대 이동 횟수라고 하면, dp(r, c) = 1 + max(dp(상), dp(하), dp(좌), dp(우)) 1. 그래프에 사이클이 존재하면 무한번 움직일 수 있다. DFS를 이용해 사이클을 확인한다. 무한번 움직일 수 있는 경우는, 그래프에 사이클이 존재하는 경우이다. DFS를 사용해서 사이클 존재여부를 체크한 후, 존재한다면 바로 -1을 출력해준다. 2. dp(r, c) = (r, c) 위치에서 시작했을 때 최대 이동 횟수라고 하면, dp(r, c) = 1 + max(dp(상), dp(하), dp(좌), dp(우)) dp(r, c) = (r,c) 위..
2022. 3. 30.
백준 12969번 ABC - C++(cpp) 풀이
1. 오름차순 쌍이 K개인 문자열 S 앞에 어떠한 문자 X를 붙여 문자열 XS를 만들었을 때, 문자열 XS가 가진 오름차순 쌍의 수는 K + (S에 포함된 X보다 큰 문자의 수)이다. 2. dp(a, b, c, k) = 'A', 'B', 'C'를 각각 a, b, c개 가지고 있으면서 오름차순 쌍이 k개인 문자열의 존재 여부 3. 따라서 'A'로 시작하는 경우, 'B'로 시작하는 경우, 'C'로 시작하는 경우를 모두 고려하면, dp(a, b, c, k) = dp(a-1, b, c, k-b-c) 또는 dp(a, b-1, c, k-c) 또는 dp(a, b, c-1, k) 1. 오름차순 쌍이 K개인 문자열 S 앞에 어떠한 문자 X를 붙여 문자열 XS를 만들었을 때, 문자열 XS가 가진 오름차순 쌍의 수는 K +..
2022. 3. 20.
