[Goorm] 구름 먼데이 챌린지 거리두기 JAVA

반응형

[Goorm[ 구름 먼데이 챌린지 거리두기

---

접근

• BFS를 이용해 모든 경우의 수
• 하나의 수식으로 완성
• 동적 프로그래밍

---

풀이

사실 문제를 풀기 전 동적 프로그래밍 유형의 문제인 걸 알고 들어갔지만 다른 방법으로도 해결이 가능할까 생각해 봤다. BFS를 사용하게 된다면 N의 범위가 너무 커 시간 초과가 날게 분명했다. 하나의 수식으로 완성을 해보려 했지만 불가능했다. 문제를 보면 1줄의 테이블로 만들 수 있는 경우의 수는 5가지로 0을 테이블 #을 스티커라 표현했을 경우 000 #00 0#0 00# #0# 왼쪽에서부터 스티커가 한 장도 없는 경우 각각 한자리마다 한 장씩 붙어있는 경우 그리고 가운데를 비우고 양 끝에 붙은 경우가 있다. 이제 한 줄의 경우의 수 5가지를 통해 Bottom-up 방식으로 값을 채워 나가면 된다. 문제에 사용할 배열을 선언해 준다.

long[][] dp = new long[n + 1][5];

int 배열로는 범위가 충분해 보이지 않기에 long으로 선언을 하고 i 줄을 기준으로 사용할 거기 때문에 배열의 크기를 한 칸 더 늘려서 선언해 준다.

dp[1][0] = 1;		//빈거
dp[1][1] = 1;		//#00
dp[1][2] = 1;		//0#0
dp[1][3] = 1;		//00#
dp[1][4] = 1;		//#0#

테이블이 1줄일 때의 값으로 초기화해준다.

for (int i = 2; i <= n; i++)

여러 줄의 테이블에 스티커를 붙여야 하기에 for문을 선언한다. 1번 테이블은 초기값을 넣어 줬기 때문에 테이블이 2 줄일 경우부터 N 줄까지 반복한다.

dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4]) % MOD;
dp[i][1] = (dp[i-1][0] + dp[i-1][2] + dp[i-1][3]) % MOD;
dp[i][2] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][3] + dp[i-1][4]) % MOD;
dp[i][3] = (dp[i-1][0] + dp[i-1][2] + dp[i-1][3]) % MOD;
dp[i][4] = (dp[i-1][0] + dp[i-1][2]) % MOD;

테이블이 여러 줄일 경우 거리 두기를 위해서는 자신의 테이블과 그전 줄의 테이블에 붙은 스티커의 위치만 고려하면 된다.그리고 갈수록 숫자가 커지기 때문에 미리미리 값을 나눠야 할 MOD(100,000,007)로 나눠준 후 값을 넣어준다.

dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4]) % MOD;
//전 줄이 아무것도 붙어 있지 않는 경우

전 줄이 아무것도 붙어 있지 않는 테이블이라면 다음 테이블은 스티커를 붙이는 모든 5가지 경우의 수가 다 올 수 있다.

dp[i][1] = (dp[i-1][0] + dp[i-1][2] + dp[i-1][3]) % MOD;
//테이블의 왼쪽에만 스티커가 붙어있는 경우

테이블의 왼쪽에만 스티커가 있다면 다음 줄에는 왼쪽에 스티커가 붙는 경우를 뺀 000, 0#0, 00# 세 가지 경우가 올 수 있다.

dp[i][2] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][3] + dp[i-1][4]) % MOD;
//테이블의 가운데만 스티커가 붙어있는 경우

마찬가지로 가운데에 스티커가 붙은 경우를 제외한 4가지 경우가 올 수 있다.

dp[i][3] = (dp[i-1][0] + dp[i-1][2] + dp[i-1][3]) % MOD;
//테이블의 오른쪽에만 스티커가 붙어있는 경우

오른쪽을 제외한 3가지

dp[i][4] = (dp[i-1][0] + dp[i-1][2]) % MOD;
//테이블 양쪽 끝에 스티커가 붙어있는 경우

양쪽 끝의 경우 비어있는 테이블과 가운데 붙어 있는 테이블 2가지 경우가 올 수 있다. 이렇게 N 줄까지 반복하게 되면 배열 dp[n][] 번지에는 스티커를 붙이는 방법 각각의 경우의 수가 더해져 들어가게 된다.

long ans = (dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4]) % MOD;

dp[n][] 번지의 모든 값을 다 더해준 뒤 100,000,007로 나눠주게 되면 정답이 된다.

---

전체 코드

import java.io.*;

class Main {
	static final int MOD = 100000007;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		long[][] dp = new long[n + 1][5];
		
		dp[1][0] = 1;		//빈거
		dp[1][1] = 1;		//#00
		dp[1][2] = 1;		//0#0
		dp[1][3] = 1;		//00#
		dp[1][4] = 1;		//#0#
		
		for (int i = 2; i <= n; i++){
			dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4]) % MOD;
			dp[i][1] = (dp[i-1][0] + dp[i-1][2] + dp[i-1][3]) % MOD;
			dp[i][2] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][3] + dp[i-1][4]) % MOD;
			dp[i][3] = (dp[i-1][0] + dp[i-1][2] + dp[i-1][3]) % MOD;
			dp[i][4] = (dp[i-1][0] + dp[i-1][2]) % MOD;
		}
		
		long ans = (dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4]) % MOD;
		
		System.out.println(ans);
	}
}

 

단순하게 생각하면 정말 쉬운 문제지만 동적 프로그래밍 유형의 문제라고 모르고 들어갔으면 수식을 찾아보며 이리저리 풀어 보력 꽤나 헤맸을 거 같다.