[BOJ] 2839: 설탕배달 (JAVA)

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

 

풀이

 

규칙을 찾아서 풀었다.

dp[12]	dp[14]	dp[16]	dp[18]	dp[20]	dp[22]	dp[24]	dp[26]	dp[28]	dp[30]
4	4	4	4	4	6	6	6	6	6

 

12번째 idx부터 idx+=2를 5번 할때까지 4봉지이고, 이후 짝수 5개는 설탕봉지 2개가 증가한 6봉지이다. 

4봉지 .. 6봉지 .. 8봉지 .. 씩 5번

dp[17]	dp[19]	dp[21]	dp[23]	dp[25]	dp[27]	dp[29]	dp[31]	dp[33]	dp[35]
5	5	5	5	5	7	7	7	7	7

 

17번째 idx부터 idx+=2를 5번 할때까지 5봉지이고, 이후 홀수 5개는 설탕보지 2개가 증가한 7봉지이다.

5봉지 .. 7봉지 .. 9봉지 .. 씩 5번

 

dp[4] 와 dp[7]은 유일하게 3봉지/5봉지로 채울 수 없기 때문에 -1

 

전체코드

package 백준renew;

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

public class 실버4_2839_설탕배달 {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());

		int dp[] = new int[5001];
		dp[3] = 1; dp[4] = -1; dp[5] = 1; dp[6] = 2; dp[7] = -1; dp[8] = 2;
		dp[9] = 3; dp[10] = 2; dp[11] = 3; dp[13] = 3; dp[15] = 3;

		int num = 4;
		int cnt = 0;
		for(int i=12; i<5001; i+=2) {
			dp[i] = num;
			cnt++;
			if(cnt == 5) {
				num+=2;
				cnt = 0;
			}
		}
		
		int n = 5;
		int c = 0;
		for(int i=17; i<5001; i+=2) {
			dp[i] = n;
			c++;
			if(c == 5) {
				n+=2;
				c = 0;
			}
		}
		
		sb.append(dp[N]);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}