백준 2193번 자바

문제

https://www.acmicpc.net/problem/2193

2193번: 이친수

import java.util.Scanner;

public class Main2193 {
	static int N;
	static long[] dp;

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		dp = new long[N+1];
		
		dp[1] = 1;
		for (int i=2; i<=N; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		System.out.println(dp[N]);
	}
}

1. 처음에 dp의 타입을 int형으로 선언했다가 오버플로우가 나면서 long으로 바꿨다. 하지만 백준에서 채점결과 틀렸습니다가 나왔을때 로직자체가 잘못된줄 알고 다른 글들을 보다가 기본형 크기의 문제라는 것을 알게됐다.

 dp[n-1] + dp[n-2]를 더하는데 초기값이 1이기에 90이 되도 그다지 큰 수가 안될거라고 생각했던게 잘못된 생각이었다.

 

2. 0자리수 0개

    1자리수 1개
    2자리수 1개 
    3자리수 2개
    4자리수 3개 
    5자리수 5개
    6자리수 8개 

6개 자리수까지 직접 구하고 수열을 발견해서 점화식을 세웠다. (i번째의 개수는 i-1 + i-2번째의 개수이다.)

이번에는 쉽게 수열을 발견해서 어렵지 않게 점화식을 세웠지만 여전히  dp문제는 쉽지 않은것 같다.

 

3. https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-2193-%EC%9E%90%EB%B0%94-%EC%9D%B4%EC%B9%9C%EC%88%98-BOJ-2193-JAVA

백준 2193 자바 - 이친수 (BOJ 2193 JAVA)

비슷한 방식으로 접근했지만 배열을 사용하지 않아 메모리를 아낀다. 이런식으로 푸는 전제 조건으로 dp를 bottom-up방식으로 풀어 나갈때 n-1, n-2만 필요하는 것을 캐치하는 것이 중요하다.

 

정리 : 정답을 맞추는거랑 별개로 다방면에서 생각을 해야 실력이 많이 늘어날 것이다. 계속해서 사고를 유연하게 유지할 수 있게 항상 고민하자.