TIL ~ 2022-02-22

1. 오늘까지 학습한 내용

백준 동적 프로그래밍 문제 9465, 2156번
사용 언어 : 자바

2. 알게 된 내용

• 9465번 - 반복문을 어떻게 묶을지도 잘 고려해야 한다.
  처음에는 아래와 같이 반복문을 2개로 나눠서 구현했었는데, 다른 분들의 코드를 보니 둘을 하나로 묶어서 구현하는 것을 볼 수 있었고 이 점이 옳은 방식이라는 것을 알게 되었다.
  1) 내가 처음에 만든 코드

for (int j = 2; j < n+1; j++) {
      dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + array[0][j];
}

for (int j = 2; j < n+1; j++) {
      dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + array[1][j];
}

2) 다른 분들의 코드를 보고 수정한 코드

for (int j = 2; j < n+1; j++) {
     dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + array[0][j];
     dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + array[1][j];
}

내가 처음에 짠 코드는 dp[0][j] 에 넣을 때 dp[0][j-1], dp[0][j-2]의 값이 대부분 0이기 때문에 제대로 동작하지 않아서 문제가 된다. 반복문만 사용하는 게 다가 아니라 그 안에 어떻게 동작하는지도 좀 더 꼼꼼하게 살펴봐야겠다.

문제 해결 시 참고한 글 : https://fbtmdwhd33.tistory.com/76

• 2156번) 점화식에 대해서 dp[2]에 관해

// n >= 3 이후인 경우
dp[1] = array[1];
dp[2] = array[1] + array[2];
for (int i = 3; i <= n; i++) {
                     //연속0번          //연속1번          //연속2번 마시는 경우
    dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+array[i], dp[i-3]+array[i-1]+array[i]));
}

만약 6, (10), (13), 9, (8), (7) 로 포도주 양이 주어졌다면 괄호로 표시한 10+13+8+7이 최댓값이 된다. 이 경우에 dp[2]까지의 값은 만약 2번째 포도주까지만 봤을 때의 최댓값을 고려하는 것이기 때문에 당연히 array[1] + array[2]가 되는 것이다. dp[3]을 구할 때부터는 for문 안에 들어가 저 코드를 실행시키면서 연속0번일 때, 연속1번일때, 연속2번일 때 중 어느 때가 가장 최댓값이 나오는지를 새로 계산해내는 것이기 때문에 dp[2] = array[1]+array[2]로 처음에 설정한 것에 대해 의문점을 가지지 않아도 된다!

참고한 출처 : https://limkydev.tistory.com/112 (설명이 이해하기 좋다)

3. 느낀 점

9465번 문제가 조금 막막하게 느껴져서 며칠동안 끌면서 공부했다... 하지만 어렵고 막히는 게 당연한거니까, 너무 막히고 풀이 갈피도 못 잡겠으면 다른 분들 설명을 조금 찾아보면서 풀이 원리를 이해해보고 코드는 스스로 짜보려고 노력해보자! 혼자 스스로 다 못했다고해서 공부를 안 한 게 아니니까 포기하지만 말자!