241020 TIL

2024년 10월 20일 작성

PS

이친수 - https://www.acmicpc.net/problem/2193

타입 실수를 자주 한다. 그리고 제출하기 전에는 의심하지 못한다. 저번 주를 기점으로 인덱스 실수는 안 하게되었는데 타입도 조심해야겠다. 릿보드보다 백준이 이런 실수를 더 많이 범하게 되는데 그 이유가 뭘까? 더 많이 풀다보면 알게되려나.

왜 난 배열 타입을 처음부터 long 으로 선언할 수 없었을까? dp 를 다룰 때 점화식을 세우고 생각하자. 이번 문제 베이스 케이스는 dp[1][1] = 1, 점화식은 dp[i][0] = dp[i-1][0] + dp[i-1][1], dp[i][1] = dp[i-1][0] 이었다. 초반의 답을 손으로 계산해 보면 값이 증가하는 속도를 알 수 있을까?

dp[1][1] = 1
dp[2][0] = 1, dp[2][1] = 1
dp[3][0] = 2, dp[3][1] = 1
dp[4][0] = 3, dp[4][1] = 2
dp[5][0] = 5, dp[5][1] = 3

음 감이 잘 안 잡힌다. 오, 답답해서 질문게시판을 찾아봤는데 나랑 같은 의문을 품은 사람이 글을 올려놨었고 거기에 답변이 달려있다.

https://www.acmicpc.net/board/view/91686

하나는 수학적으로 예측해보는 방식, 그리고 다른 하나는 최대 크기까지 돌려보는 방법을 추천했다. 나는 전자는 이해하기 어려워서 후자를 시도해봤다.

for (int i = 2; i <= N; i++) {
    // 1을 붙이는 경우
    dp[i][1] = dp[i - 1][0];
    // 0을 붙이는 경우
    if (dp[i - 1][0] >= Integer.MAX_VALUE || dp[i - 1][1] >= Integer.MAX_VALUE) {
		    **System.out.println(i - 1);**
    }
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
}

최대 N(=90)을 입력으로 돌려보니 무려 48자리 부터 경우의 수가 int 범위를 벗어나는 것을 알 수 있었다.

질문게시판 보니까 재밌다. 사소한 실수가 참 많은데 예전엔 물어볼 사람이 따로 있는게 아니면 나라도 엄청 헤맸을 것 같다. 문명이 발전하고 있구만요