[백준] 1309 - 동물원 (JAVA)

1. 소요시간 : 9분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 1
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/1309
8. 푼 날짜 : 2023.03.19

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.

2. 사고과정

이번 문제도 직접 그려봄으로써 풀이를 할 수 있었다.
1부터 3까지 그려봤을 때 solution을 알게 되었다. 아마 4를 그리라고 했으면 너무 복잡해서 못그렸을 것 같다.
그런데 테스트케이스에 떡하니 4의 답이 주어진 게 아니겠는가. 보통 n이 2일때 정도의 테스트케이스의 답을 주는데 여기서는 무려 4의 answer를 줬다. 단지 이것 때문만이라도 이 문제의 난이도가 1단계 낮아질 정도로 엄청난 단서였다.

3. 풀이과정

점화식은 dp[i]=dp[i-2]+dp[i-1]x2 이다.

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		
		int dp[]=new int[100001];
		
		dp[1]=3;
		dp[2]=7;
		for(int i=3;i<dp.length;i++) {
			dp[i]=(dp[i-2]+dp[i-1]*2)%9901;
		}
		int n=Integer.parseInt(br.readLine());
		System.out.println(dp[n]);
		
		
		
	}
}

5. 결과

6. 회고

냅색 문제... 다시 도전해봐야겠지 ?

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212