[백준] 14916번: 거스름돈 자바(Java)

문제

---

14916번: 거스름돈

 

접근법

---

첫 접근 (잘못된 접근)

처음 접근을 n이 홀수일 때와 짝수일 때를 나눠서 했다.

n이 짝수일때는 5를 최대로 나눠도 나눈 나머지가 2로 항상 나누어 떨어지기 때문에 상관이 없다.

하지만, n이 홀수일 때는 5로 나누는 순간 2로 나누어 떨어질수 없기 때문에, 5를 한번 덜 나누어 줬다. 무슨 말이냐면, 예를 들어 n=13일 때, 5로 나누게 되면 몫이 2이고, 나머지가 3이다. 3은 2로 나누어 떨어질 수 없기 때문에 5로 나눈 몫을 1로 바꾸고 나머지를 8로 바꿔서 계산한다는 의미이다.

이렇게 하면 웬만한 예제는 모두 정답이 나온다. 하지만 문제는 5, 15, 25 같은 홀수 중 5로 완전히 나누어 떨어지는 경우에 나타났다.

따라서, 이 접근은 틀렸다고 판단하고 다른 접근을 시도해보았다.

두번째 접근

현재 나는 처음의 n이 홀수인지, 짝수인지를 if문으로 경우를 나누면서 시작하기 때문에 문제가 발생하였다. 그렇다면, n을 5로 나눈 직후의 나머지가 홀수인지 짝수인지를 확인하면 되는 것 아닌가?

이 개념이 바로 동적 프로그래밍(DP) 개념이다.

n을 5로 나눈 몫이 홀수라면, 첫번째 접근처럼 5로 나눈 몫을 1 감소, 5로 나눈 나머지를 5 증가 시키면 된다.

if (n % 2 != 0) { //5로 나눈 나머지가 홀수인 경우
          num_of_charge --;
          n += 5;
}

여기서도 문제가 발생했다. 그렇다면 거슬러지지 않는 수 (ex. 1 또는 3)은 어떻게 처리할 것인가?

물론 손쉽게 if문으로 빼서 return을 사용하면 된다. 하지만 문제의도는 그게 아니다. 1과 3의 특징을 자세히 보면, 모두 5보다는 작으면서 홀수인 수들이다.

이를 적용하여 n으로 나누었을 때의 if문 조건을 다음과 같이 바꿔준다.

if (num_of_charge != 0 && n % 2 != 0) { //5로 나누어 지는 수 중, 5로 나눈 나머지가 홀수인 경우
          num_of_charge --;
          n += 5;
}

→ 5로 나누었을 때 몫이 0이 라는 것은 5로 나누어지지 않는, 즉 5보다 작은 수를 나타내기 때문에 이런 조건을 추가할 수 있다.

 

풀이

---

import java.io.*;

public class Main {
    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());

        int[] charges = {5,2};
        int num_of_charge = 0;

        num_of_charge += n / charges[0];
        n %= charges[0];

        if (num_of_charge != 0 && n % 2 != 0) { //5로 나눠졌을 때, 나머지가 홀수인 경우
            num_of_charge --;
            n += 5;
        }

        num_of_charge += n / charges[1];
        n %= charges[1];

        if (n != 0) {
            bw.write(String.valueOf(-1));
            bw.flush();
            return;
        }

        bw.write(String.valueOf(num_of_charge));
        bw.flush();

    }
}