[백준] 2747 - 피보나치 수 (Java)

정답과 결론은 맨 아래에-!!

이전 포스터로 작성한 2xn 타일링과 같은 dp 알고리즘을 활용한 문제입니다.
dp의 더 자세한 설명은 이곳 을 통해 확인해주세요.

문제 이해

dp에서 반복문 타입으로 문제를 풀었으며 이 전에 포스트 한 2xn보다는 쉽게 풀 수 있었다.

• n으로 숫자를 받는다고 할 때 n보다 1 작은 숫자와 2작은 숫자의 값을 더하는 것이다.
• 예를 들면 숫자 3을 입력했을 때 1의 값 + 2의 값을 더한 것이 3의 값이 된다.
• 주의할 점은 1+2가 아니라 위치 1의 값과 위치 2의 값을 더한 것이어야 한다는 점이다.
• 시작하는 위치는 0번째 부터니까 0=0, 1=1로 값을 넣은 후 2=1, 3=2 이렇게 점차 증가해나가는 방식이다.
• 문제를 읽으면 n번째 값을 구하는 것인데, 0부터 숫자가 시작하기 때문에 초반에 n을 입력받고 dp 배열을 구성할 때 n+1로 만들어야 한다.

입출력 형식

• 숫자 n을 입력받은 후 n번째에 들어있는 값을 출력하면 된다.
• n은 45보다 작거나 같기 때문에 모두 더한 값이 int 범위를 넘기지는 않는다. (int의 양수 범위는 21억정도 된다.)

코드 이해

반복문을 이용한 dp를 이용하였고, main에서는 n을 입력받고 dp의 배열 사이즈를 선언하였다.
반복문이 돌아가는 메인코드는 solve라는 메소드로 따로 빼서 만들었다.
만약 n이 0,1,2일 때는 바로 값이 반환되도록 했다.
그 이상일 경우 하단의 코드가 돌아가는데 이 때 dp 배열의 0번째와 1번째는 값을 미리 넣어두고 2번째 배열부터 반복문을 돌렸다.
그리고 dp의 n번째 값을 바로 반환하여 main메소드에서 따로 변수를 설정하지 않고 값이 바로 출력되도록 했다.

한줄평

dp알고리즘을 확실하게 알고나니까 이 문제는 쉽게 응용해서 풀 수 있었다.
dp알고리즘 문제를 더 풀어서 개념을 더 확고하게 하고, 응용한 어려운 문제들도 풀어봐야겠다는 생각이 든다.