[Java] 6단계. 체스판 다시 칠하기 [2839번]

• 예제 입력1

18

• 예제 출력1

4

• 예제 입력2

4

• 예제 출력2

-1

 

• 예제 입력3

6

• 예제 출력3

2

• 예제 입력4

9

• 예제 출력4

3

• 예제 입력5

11

• 예제 출력5

3

 

---

 

• 문제 접근
  • 그리디 알고리즘처럼 풀게 되면 다음과 같은 예시는 해결 불가
    • 21kg → 5kg 4개로 1kg 남아 -1을 출력하게 됨
    • 원래 정답은 3kg 7개로 7이 되어야 함
• 문제 해결
  • 최소 봉지가 되려면 5kg을 최대한 많이 들고, 나머지를 3kg로 채워야 함
  • N이 5로 나누어 떨어지면 그것이 최소 봉지
  • N이 5로 나누어 떨어지지 않을 경우
    • N / 5의 몫을 저장,  N - (몫 * 5) = 나머지
    • 나머지가 3의 배수일 경우 (몫 + 나머지/3)를 저장하고 반복문 종료
    • 나머지가 3의 배수가 아니면 몫을 1개 차감하고 다시 반복
• 슈도 코드

N (kg 저장)
count에 -1 저장
if(N이 5의 배수면 저장){
	count에 N / 5 저장
}else {
	quotient에 N/5 저장
	for(i = quotient가 0이상일 때까지 반복){
		remainder에 N - 5 * quotient 저장
		if(remainder가 3의 배수라면){
			count에 i + remainder/3의 값 저장
			break; (최소 봉지이기 때문)
		}
	}
}
count 출력

• 코딩하기

public static void main(String[] args) throws Exception{
    Scanner scan = new Scanner(System.in);
    int N = scan.nextInt();
    scan.close();
    int count = -1;
    if(N % 5 == 0){
        count = N / 5;
    } else {
        int quotient = N / 5;
        for(int i = quotient; i >= 0; i--){
            int remainder = N - (i * 5);
            if(remainder % 3 == 0){
                count = i + remainder/3;
                break;
            }
        }
    }
    System.out.println(count);
}