99클럽 코테 스터디 14일차 TIL (미들러): [백준][Java] 14916 거스름돈 - 실버5

 

문제 보기

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

 

 

풀이

힌트를 보면 그리드, DP를 사용할 수 있는 문제인 것 같다.

나는 DP가 더 익숙해서 DP를 사용하였다.

즉 거스름 돈이 0부터 N원일 때까지 얼마가 나올지를 계산해보는 방법을 선택했다.

 

int[] dp = new int[N < 5 ? 6 : N + 1];
dp[0] = 100000;
dp[1] = 100000;
dp[2] = 1;
dp[3] = 100000;
dp[4] = 2;
dp[5] = 1;

우선 0~5까지는 미리 값을 계산하여 넣어 놨다.

혹시나 input으로 5보다 작은 값이 들어올 경우에도 dp 배열의 크기를 6으로 하도록 했다.

여기서 -1이 나와야 하는 값의 경우 100000이라는, 절대 나올리 없는 임의의 큰 값을 넣었다.

 

for (int i = 6; i <= N; i++) {
  dp[i] = Math.min(dp[i - 5], dp[i - 2]) + 1;
}

이후 반복문을 돌리며

5원 더 작은 값에서 5원을 추가한 상황,

2원 더 작은 값에서 2원을 추가한 상황 중 더 작은 경우를 골랐다.

만약 -1값이 나와야 하는 상황이어도 터무니없이 큰 수가 나오며 걸러질 테니 괜찮다.

 

if(dp[N] >= 100000) {
  bw.write(-1 + "\n");
} else {
  bw.write(dp[N] + "\n");
}

결과적으로 경우의 수가 없다면 100000 이상의 값이 되니 -1을 출력한다.

아닐 경우 dp[N]의 값을 출력한다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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[] dp = new int[N < 5 ? 6 : N + 1];
    dp[0] = 100000;
    dp[1] = 100000;
    dp[2] = 1;
    dp[3] = 100000;
    dp[4] = 2;
    dp[5] = 1;
    for (int i = 6; i <= N; i++) {
      dp[i] = Math.min(dp[i - 5], dp[i - 2]) + 1;
    }

    if(dp[N] >= 100000) {
      bw.write(-1 + "\n");
    } else {
      bw.write(dp[N] + "\n");
    }

    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Silver/14916.%E2%80%85%EA%B1%B0%EC%8A%A4%EB%A6%84%EB%8F%88

CodingTest_AutoSave/백준/Silver/14916. 거스름돈 at main · MetroDefro/CodingTest_AutoSave