TIL 2022-02-15 화

1. 오늘 학습한 내용

백준 동적프로그래밍 문제 11057번
사용 언어 : 자바
내가 푼 코드 : https://github.com/MinYeongPark/Coding/blob/main/baekjoon/n11057.java

2. 알게 된 내용

• 메모이제이션 할 배열의 크기를 지정할 때
  처음에는 N이 1 ~ 1000이라길래 1001 (편의 상 0번 인덱스는 사용 안 하려고 했음)의 크기로 지정하려고 했는데 너무 비효율적인 크기였다. 다른 분의 코드를 보니 그냥 딱 (입력받는 N의 값) + 1 만큼 배열의 크기를 지정하면 된다는 것을 알게 되었다. 앞으로 이렇게 효율적인 배열의 크기를 생각하면서 코드를 구현하자.

int dp[][] = new int[input+1][10]; //여기서 [input+1]

• 메모이제이션 하기 전에 % 10007을 해서 그 값을 넣자!

for (int i = 2; i <= input; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = j; k < 10; k++) {
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= 10007;
                }
            }
        }

이 부분은 다른 분의 코드를 보고 이해한 후에 변경한 코드인데, 원래 처음에

dp[i][j] += dp[i-1][k] % 10007;

로 했었는데, 이 방법은 dp[i][j]값을 오버플로우 시킬 수도 있기 때문에 최적으로 만들어주는 게 아니므로 일단 더한 후 나중에 % 10007을 진행해야 한다는 것을 잊지 말자!

참고한 출처 : https://www.acmicpc.net/board/view/35003

• 동적 프로그래밍 문제 풀 때 표 적극 활용하기
  그동안 푼 문제들 설명을 찾아봤을 때 다들 서로 표나 그래프 등등으로 관계를 파악해가면서 점화식을 찾으셨는데, 나도 비슷하게 한번 표 형식으로 원리를 찾아가면서 풀어보았더니 얼추 원리가 딱 맞게 되었다. 표나 그래프 등등으로 작은 예시부터 넣어보면서 규칙을 잘 찾아보자!

느낀 점

어제 공부했던 원리를 바탕으로 오늘 스스로 점화식을 찾아보고 원리를 파악하면서 얼추 비슷하게 풀어서 정말 뿌듯하다. 비록 자잘한 부분들이 조금 빗나가서 바로 '맞았습니다'가 뜨지는 못했지만 그래도 중심 원리를 잘 파악한 것 같아서 다행이다. 앞으로는 자잘한 부분들도 꼼꼼히 확인하고 코드를 짜도록 노력해야겠다.