[23/05/04] B2839

Dynamic Programming : 큰 문제를 작은 문제로 쪼개서 작은 문제를 해결함으로써 큰 문제도 해결하는 방법

 

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
 
public class B2839 {
 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
 
		if (N == 4 || N == 7) {
			System.out.println(-1);
		}
		else if (N % 5 == 0) {
			System.out.println(N / 5);
		}
		else if (N % 5 == 1 || N % 5 == 3) {
			System.out.println((N / 5) + 1);
		}
		else if (N % 5 == 2 || N % 5 == 4) {
			System.out.println((N / 5) + 2);
		}
	}
}

 

 

 

 

느낀점

최소한의 봉지 개수를 구하는 것이 목표임을 까먹지 말자

그래서 방식이

1. 큰 수로 구성해보기

2. 큰 수로 구성해본 것에서 작은 수로 구성해보기

3. 최소한으로 작은 수로 구성해본 후 큰 수로 구성해보기

4. (큰 수-1)를 구성해본 후 큰 수로 구성해보기

5. 불가능 채우기, 남은 수 직접 계산해서 채우기

 

그리고 또 기억할 것은

불가능(4,7)은 가장 먼저 분기처리해야 한다!