[프로그래머스 lv3] 등굣길 풀이
해설오른쪽과 아래쪽으로 이동하고, 특정 지점을 향하는 문제는 dp의 전형적인 유형이다. dfs(int x, int y) 를 (x, y)에서 (n, m)까지 이동하는 경우의 수라고 정의할 때 이동할 수 있는 방법은 두 가지가 있다.1) 오른쪽 방향: (x, y+1)에서 (n, m)으로 이동하는 방법2) 아래쪽 방향: (x+1, y)에서 (n, m)으로 이동하는 방법따라서, dfs(x, y)는 dfs(x, y+1) + dfs(x+1, y) 로 정의할 수 있다. 이때, 메모이제이션 없이 dfs를 돌려버리면 TLE가 발생할 가능성이 높으므로 이미 구한 값을 저장해놓고 해당 결과가 필요할 때마다 찾아 쓰는 동적프로그래밍 방법을 사용하자.dfs(int x, int y)가 실행되었을 때, 그 결과가 이미 memo[x..
2022. 9. 8.
[프로그래머스 lv3] 최고의 집합 풀이
해설가장 단순하게 백트래킹 방법이 떠오르지만, 백트래킹으로 n개의 합이 S가 되는 모든 경우를 탐색하면 TLE가 발생한다.dp 점화식도 세울 수 있지만, n과 s의 입력범위가 너무 커 해당 방법도 TLE가 날 것이 분명하다. 이 문제는 완전 탐색 없이 간단한 트릭을 통해 해결할 수 있다.특정 배열의 원소의 곱이 최대가 되려면, 각 원소가 최대한 균등해야 한다.예를 들어 n = 4 이고 s = 10일 때, 각 원소를 최대한 균등하게 하려면 s/n = 10/4 = 2 를 4개 마련하고 {2, 2, 2, 2} 여기에 나머지 2를 하나씩 더해준다. 결과적으로 {2, 2, 3, 3}이 최대 곱을 만드는 배열이 된다. n > s 이면 자연수 n개의합이 s가 되는 경우가 없으므로 {-1}을 리턴한다.n 최종 배열을 ..
2022. 9. 4.