[99club/TIL] 6주차 - 토요일 TIL(Today I Learned)

안녕하세요. delay100 입니다!

---

미들러 문제

---

1번. 동물원

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

dp로 풀어줍니다. 2차원 배열을 사용했습니다.

list[i][0] = 아무곳에도 사자를 넣지 않는 경우의 수

list[i][1] = 왼쪽에만 사자를 넣은 경우의 수

list[i][2] = 오른쪽에만 사자를 넣은 경우의 수

각각 i번째에 각각 경우의 수를 갱신해줍니다.

배열의 내부 값이 매우 커지기 때문에 연산 시 %9901을 계속 해주었습니다.

import java.io.*;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int[][] list = new int[100001][3];
		
		list[1][0] = list[1][1] = list[1][2] = 1;
		
		for(int i=2; i<=N; i++) {
			// 둘다 아무것도 안 넣는 경우
			list[i][0] = (list[i-1][0] + list[i-1][1] + list[i-1][2]) % 9901;
			// 왼쪽에만 넣는 경우
			list[i][1] = (list[i-1][0] + list[i-1][2]) % 9901;
			// 오른쪽에만 넣는 경우
			list[i][2] = (list[i-1][0] + list[i-1][2]) % 9901;
		}
		
		bw.write(Integer.toString((list[N][0]+list[N][1]+list[N][2])%9901));
		
		
		br.close();
		bw.close();
	}
}

[참고한 블로그]

 

https://velog.io/@sungjin0757/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-1309%EB%B2%88-%EB%8F%99%EB%AC%BC%EC%9B%90-JAVA

[알고리즘] - 백준 1309번 : 동물원 (JAVA)

---

+ 비기너 문제

달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869

+ 챌린저 문제

계단 오르기 https://www.acmicpc.net/problem/2579

---

봐주셔서 감사합니다. 피드백 환영합니다.