2021년 8월 21일 토요일 - 이번에도 오랜만에 백준 풀이를 올린다..!
오늘 올려볼 문제는 2294번 동전 2 라는 문제이다.
사진을 클릭하면 해당 문제로 이동합니다.
오늘은 채점 현황표를 보다가 한 문제 선택해서 가지고왔다!
문제 고르는 것도 문제 푸는 것만큼 어려운 듯..
입력 예제
입력은 딱 봐도 알아볼 수 있는 입력이다.
풀이 및 코드
이 문제의 알고리즘 분류가 다이나믹 프로그래밍으로 되어있는데 나는 처음에 이를 무시하고 직관대로 풀었다!
그 결과...
제출 화면
값이 큰 동전부터 차례대로 동전의 개수를 구한다고 해서 최소가 아닐 수 있다는 것을 깨닫고... 다이나믹 프로그래밍을 통해서 문제를 해결했다...
자세한 설명은 코드를 보면서 하자!
풀이코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
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));
// 입력받기
String[] input_num = br.readLine().split(" ");
// int로 바꾸기
int n = Integer.parseInt(input_num[0]), k = Integer.parseInt(input_num[1]);
// 동전의 가치를 저장할 배열, dp를 위한 배열 2개를 선언(dp배열의 크기는 넉넉하게 잡아두는 것이 좋다.)
// dp는 동전의 개수를 저장한다고 생각하면 된다.
int[] arr = new int[n], dp = new int[150000];
// 입력받아서 동전의 가치를 배열에 저장
for(int i = 0; i < n; i++)
{
arr[i] = Integer.parseInt(br.readLine());
}
// dp배열을 큰 수로 채운다. (동전 개수의 최솟값을 구하는 것이기 때문에 큰 수를 저장해두면 편하다.)
Arrays.fill(dp, Integer.MAX_VALUE);
// 입력받은 동전의 가치가 정렬되어 있지 않을 수 있기 때문에 정렬을 시행해준다.
Arrays.sort(arr);
// 작은 가치를 가진 동전부터 k가 될 때까지 동전의 개수를 dp에 저장하면서 센다.
// 이 때 더욱 적은 동전으로 해당 값을 표현할 수 있으면 적은 개수를 저장한다.
for(int i = 0; i < n; i++)
{
// arr[i]에 해당하는 가치는 arr[i] 동전 하나로 표현 가능하므로 해당 dp를 동전 1개로 설정해둔다.
dp[arr[i]] = 1;
// k만큼 dp를 살펴본다.
for(int j = 0; j <= k; j++)
{
// 만약 dp[j]가 큰수가 아니라면 (즉 입력받은 동전들로 만들 수 있는 값이라면)
if(dp[j] != Integer.MAX_VALUE)
{
// (현재 j값 + 동전의 가치)에 저장되어있는 동전의 개수와 와 (현재 j값)에 저장되어 있는 동전의 개수 + 1 중 더 작은 값을 dp[j + arr[i]]에 저장한다.
dp[j + arr[i]] = Math.min(dp[j + arr[i]], dp[j] + 1);
}
}
}
// 만약 dp[k]가 큰수라면 (동전들로 만들 수 없는 값이라면)
if(dp[k] == Integer.MAX_VALUE)
{
// -1을 출력한다.
bw.write("-1");
}
// 아니라면
else
{
// dp[k]를 출력한다.
bw.write(dp[k] + "\n");
}
bw.flush();
}
}제출 화면
오늘 문제는 자칫하면 잘못 풀 가능성이 큰 문제를 가져왔다.
항상 직관을 믿지말고 데이터를 믿자!
'백준 문제 풀이' 카테고리의 다른 글
| [BOJ / 백준] 백준 1120번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.30 |
|---|---|
| [BOJ / 백준] 백준 11399번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.29 |
| [BOJ / 백준] 백준 2799번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.14 |
| [BOJ / 백준] 백준 2493번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.02 |
| [BOJ / 백준] 백준 17298번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.30 |