[Java] 백준 1562 - 개근상

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

1563번: 개근상

3번의 시도 끝에 성공

 

N+1까지 경우의 수를 계속 붙여가면서 진행했는데, 내가 생각해낸 건 3가지 경우다

• O : 출석 1번
• AO : 연속된 결석 1번
• AAO : 연속된 결석 2번

그리고 마지막이 A로 끝나는 경우를 대비하여 N+1까지 찾은 후, 마지막 O를 빼버렸다.

또 지각은 N+1까지 찾은 후 O를 빼고, O들 중 하나를 L로 바꾸는 방식으로 함

 

1차시도 : BFS  → 메모리 초과 (C++로도 해봤는데 똑같음)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
private static int mod = 1000000;
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());
N++;

// 지각을 2번 이상 했거나 결석을 세 번 연속으로 한 사람

int sum =0;

// int[] -> {O개수, 총 개수};
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {0,0});

while(!q.isEmpty()) {
int[] now = q.poll();
int oCnt = now[0];
int sCnt = now[1];

// O or AO or AAO
for(int i=1; i<=3; i++) {
int noCnt = oCnt + 1;
int nsCnt = sCnt + i;

if(nsCnt == N) {
// sum += noCnt -1 + 1;
sum += noCnt % mod;
break;
}

q.add(new int[] {noCnt, nsCnt});
}
}
sum %= mod;
bw.write(sum+"");
bw.flush();
bw.close();
}
}

2차시도 : DFS → 시간 초과 (Queue가 계속 메모리 차지해서 그런가 싶어서 변경, 하지만 시간초과 ㅋㅋ)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
private static int mod = 1000000, sum = 0 , N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

N = Integer.parseInt(br.readLine());
N++;

// 지각을 2번 이상 했거나 결석을 세 번 연속으로 한 사람

dfs(0,0);

sum %= mod;
bw.write(sum+"");
bw.flush();
bw.close();
}

public static void dfs(int oCnt, int sCnt) {
for(int i=1; i<=3; i++) {
int noCnt = oCnt + 1;
int nsCnt = sCnt + i;

if(nsCnt == N) {
// sum += noCnt -1 + 1;
sum += noCnt % mod;
return ;
}

dfs(noCnt, nsCnt);
}
}
}

3차시도 : DP → 성공!!

※ 메모리 제한은 128MB이고, https://www.acmicpc.net/board/view/24015 이 글을 읽어보면 좋을거같다.

 

변경된 방법

DP[출결 개수][지각 개수][연속 결석 개수] = 앞의 조건들을 만족하는 경우의 수

 

경우의 수는 총 6가지

• 지각 0 연속결석 0 (이전에 연속결석 1, 2인 경우 포함)
• 지각1 연속결석0
• 지각0 연속결석1
• 지각0 연속결석2
• 지각1 연속결석1
• 지각1 연속결석2 (이전이 무조건 결석이어야 함)

 

[코드]

package BOJ_1000;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;


public class boj1563 {
	private static int[][][] attend;
	private static int mod = 1000000, N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		
		// [출결 수] [지각 수] [연속 결석 수]
		attend = new int[N+1][2][3];
		attend[1][0][0] = attend[1][1][0] = attend[1][0][1] = 1;
		
		for(int i=2; i<=N; i++) {
			attend[i][0][0] = (attend[i-1][0][0] + attend[i-1][0][1] + attend[i-1][0][2]) % mod;
			attend[i][1][0] = (attend[i-1][0][0] + attend[i-1][1][0] + attend[i-1][0][1] + attend[i-1][0][2]  + attend[i-1][1][1] + attend[i-1][1][2]) % mod;
			attend[i][0][1] = attend[i-1][0][0] % mod; 
			attend[i][1][1] = attend[i-1][1][0] % mod;
			attend[i][0][2] = attend[i-1][0][1] % mod;
			attend[i][1][2] = attend[i-1][1][1] % mod;
		}
		
		int sum = (attend[N][0][0]+attend[N][1][0]+attend[N][0][1]+attend[N][0][2]+attend[N][1][1]+attend[N][1][2])%mod;
		
		
		bw.write(sum+"");
		bw.flush();
		bw.close();
	}
	
}