김연섭 / 3기 3주차 / 3문제

[dustjq1004]

문제명 : 외계인 침공

시간 복잡도 : O(n) , 공간 복잡도 :

1. 풀이 과정

문제 요구사항은 개구리를 납치할 수 있는 최대 값입니다. 즉 모든 경우의 수를 탐색해야하는데 입력 값의 범위를 생각하면 최적화가 필요한 문제입니다. 그렇기 때문에 DP문제라는 것을 유추해볼 수 있습니다. 또는 이분탐색으로 최적화할 수도 있다고 합니다. DP로 생각한 풀이는 다음과 같습니다. 가장 중요한 것은 침공을 하게되면 침공한 나라 +-1 주변 나라는 침공해도 납치할 수 없다는 조건이 입니다. 이는 i를 침공하면 최소 i + 1는 침공할 수 없다는 얘기입니다. 또는 i를 선택안하면 i+1은 침공할 수 있습니다. 그렇게 생각해서 점화식을 유추해보면 dp[i - 2] + dp[i] 이거나 dp[i-1] 둘 중 하나를 선택할 수 있습니다.

dp[n] =  max(dp[i -2] + arr[i],  dp[i-1])

위와 같은 점화식을 세울 수 있었습니다.

---

문제명 : 내리막길

시간 복잡도 : , 공간 복잡도 :

1. 풀이 과정

DFS와 dp를 사용해 최적화해서 문제를 풀었습니다. dfs만으로는 모든 방향을 탐색하기엔 불가능 합니다. 그렇기 때문에 dp를 사용하여 이전에 탐색했던 경로를 저장하도록 문제를 풀었습니다.

---

문제명 : 1, 2, 3 더하기 4

시간 복잡도 : , 공간 복잡도 :

1. 풀이 과정

다른 사람 풀이를 보고 문제를 풀었습니다. 문제 풀이는 다음과 같습니다.

더하기 가장 끝에 있는 숫자가 1이 되거나 2,3이 되어 숫자 n을 만들 수 있는 경우의 수를 저장하고 다음 n을 구할 때 이전 갯수를 사용했습니다.

dp[i][1] = dp[i - 1][1];
dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];