220505_w3_DP - Sunny-W-Park/elice-sw2-algorithms GitHub Wiki

박선우 - #14501 퇴사

• 문제 보기(출처)
• 풀이 코드

문제 해석

• N: 상담 가능한 남은 일 수(N+1일에 퇴사)
• N개의 줄에 Ti(상담 소요 일)와 Pi(금액)가 주어짐
• 각 상담을 시작하면 상담이 끝날 때까지 다른 상담은 할 수 없음. N일 간 얻을 수 있는 최대 금액을 구하라
  • 1일 차 Ti=3, Pi=10 이라면 1,2,3일 차까지 다른 상담 못함, 금액 10
  • 4일 차 Ti=1, Pi=20 이라면 4일 차까지 다른 상담 못함, 누적 금액 10+20 = 30

접근

• dp 활용 각 idx의 dp값은 해당 일자까지 금액의 최대값
• N일 차부터 Ti, Pi값을 거꾸로 확인하면서
  • 상담이 가능한지(i + Ti < N)
  • 누적 값이 최대인지 확인

풀이 과정

• table 배열 내에 [Ti, Pi] 값을 배열로 저장
• for문: N-1부터 -1까지 table을 거꾸로 확인
• i + table[i][0] > N 일 경우 상담 불가 -> 이전 dp값과 동일한 dp[i+1]을 저장 -> dp[i] = dp[i+1]
• i + table[i][0] <= N 일 경우 상담 가능 -> 최대값 비교(이전 dp값, 상담 진행 시 금액) -> max(dp[i+1], dp[i+table[i][0]]+table[i][1])

---

백성호 - #2011 암호코드

• 문제 보기(출처)
• 풀이 코드

문제 해석

• 알파벳으로 이루어진 문자열을 숫자(1-26)로 암호화 해서 하나의 긴 숫자로 만든다. 이 때 숫자를 다시 알파벳으로 변환하여 해석할 경우, 해석 가능한 문자열의 경우의 수를 구해야 한다.
• 하나의 숫자로 이루어진 암호가 입력으로 주어졌을 때, 가능한 해석의 가짓수를 1000000으로 나눈 나머지를 출력한다.

접근

• 가장 기본적인 상황은 N개의 숫자가 있을 경우, 앞의 N-1개의 숫자에 N번째 수를 추가하는 경우와 N-2개의 숫자에 N-1번째 수와 N-2번째 수를 함께 추가하는 경우이다.
• 점화식 DP(N) = DP(N-1)+DP(N-2)
• 그러나 추가되는 숫자가 0이거나 27 이상일 경우를 예외 처리를 해야 한다.

풀이 과정

• 숫자를 문자열로 입력 받는다.
• dp를 (코드 문자열의 길이+1)만큼 0으로 이루어진 배열로 초기화 한다. *문자열의 길이가 1인데 입력이 0인 경우, 불가능한 암호이므로 0을 출력하고, 프로그램을 종료한다.
• 문자열의 길이가 1이고, 0 이 아닌 경우 1가지 경우가 가능하므로 1을 출력하고, 프로그램을 종료한다.
• 문자열의 길이가 2부터 문자열 N까지, dp[2]~dp[N]을 구해야 한다. 초기값으로 dp[0]=1, dp[1]=1을 설정한다. 평범한 상황에 dp[2]=dp[1]+dp[0]=2 이고, 특수 상황인 203 같은 경우도 20/3 으로만 해석이 가능한데 이것도 경우의 수가 1이라 편리를 위해 dp[0]도 1로 설정한다.
• dp의 N번째 경우를 구할 경우, 예시로 …..3421 에서 1이 N번째 수일 때, 두 자리 수로 추가 할 수 있는 21, N-1번째 수 2, N번째 수 1을 모두 상수로 변환 후 변수에 저장한다.
• 만약에 0이 연속으로 두 번 있거나, 30같이 3/0 과 30같이 둘 다 해석이 불가능하다면, 불가능한 암호이므로 0을 출력하고 프로그램을 종료한다. *만약에 51같이 26보다 크지만, 5/1 로는 해석이 가능한 경우는 dp[n]=dp[n-1]이 성립한다.
• 만약에 10 같이 26보다 작지만, 1/0 으로는 해석이 불가능한 경우는 dp[n]= dp[n-2]가 성립한다. *만약에 2201 같은 경우는 2/20/1 같이 해석이 가능하다, 이 때 201 부분은 1가지 경우만 가능하므로, 06 같이 그전 수가 0인 경우는 dp[n]=dp[n-3]이 성립한다. *그 외의 평범한 경우에는 dp[n]=(dp[n-1]+dp[n-2])%1000000 이 성립한다. *dp 배열의 마지막인 dp[-1]을 출력한다.

---

지의신 - #12865 평범한배낭 DP

• 문제 보기(출처)
• 풀이 코드

문제 해석

• 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 하는 것
• 전형적인 냅색 알고리즘이다. 담을 수 있는 물건이 나누어 질 수 없을 때 이므로 0-1 배낭문제라고 한다.

접근

• 2차원 배열을 만들어 값을 계속 갱신해나간다. 모든 경우의 수를 고려하는 것이다.
• 모든 짐들을 i(세로)로, 그리고 무게 K를 j(가로)로 2중 반복문을 돌린다.

풀이 과정

• j가 해당 짐의 무게보다 작다면 knapsack[i-1][j] (같은 j이 일때 제일 최신의 값)
• j가 해당 짐의 무게보다 크거나 같다면 knapsack[i-1][j]와 해당짐의 가치+knapsack[i-1][j-해당 짐의 무게] 둘중 큰것으로 갱신한다.
• knapsack[n][k]값을 출력한다.

---

김재민 - #1463 1로 만들기

• 문제 보기(출처)
• 풀이 코드

문제 해석

• 주어진 정수 N에 대하여 2로 나누거나 3으로 나누거나 1을 빼서 1로 만든다

접근

• 최적해를 dp배열 index N에 저장
• 2로 나누어 진다면 count 1과 N에서 2로 나누고 난 나머지 dp[N//2] 최적해 count를 더한값을 index N에 저장해나간다. 3의 경우도 마찬가지이며 이외 경우는 count1과바로 전 dp[N-1] count를 더한다
• 점화식 N이 2로 나누어 떨어질때 DP(N) = 1 + dp[N//2] 3으로 나누어 떨어질때 DP(N) = 1 + dp[N//3] 이외 DP(N) = 1 + dp[N-1]

풀이 과정

• 숫자를 문자열로 입력 받는다.
• dp 배열에 N이 0일 경우, 1일 경우, 2일 경우, 3일 경우 최적해를 넣는다.
• N이 4이상이라면 for문이 돌아간다.
• 2로 나눈 최적해와 3으로 나눈 최적해, 바로 전 최적해 중 가장 최소인 값을 찾기 위해 min_arr를 무한대로 초기화 한다.
• 2로 나누어 진다면 count 1과 N에서 2로 나누고 난 나머지 dp[N//2] 최적해 count를 더한값을 index N에 저장해나간다. 3의 경우도 마찬가지이며 이외 경우는 count1과바로 전 dp[N-1] count를 더한다
• min_arr에서 2로 나눈 최적해는 0, 3으로 나눈 최적해는 1, -1을 한 최적해는 3에 대입하여 최소를 구한다.
• 최소인 최적해를 dp에 대입한다.
• N의 최적해인 dp[X]값을 출력한다.