문제
접근 방식
예제의 답을 직접 구해보니 그리디로 현재 갖고 있는 금액(M)으로 구매 가능한 가장 큰 수를 맨 앞자리로 설정하고, 남은 금액으로 같은 작업을 반복해서 진행하는 식으로 구하면 될 것 같다고 생각했다.
그러나 다음 아이디어를 떠올렸다.
- 무조건 큰 수만 많이 차지하면 안 된다. 작은 수를 택하더라도 자릿수가 커야 한다.
- 최대로 만들 수 있는 자릿수를 먼저 구한 후, 그 자릿수 안에서 최댓값을 구하면 되지 않을까?
- 자릿수를 최대로 만든다. -> M에서 선택한 숫자들의 가격의 합을 빼 남은 가격을 구한다. -> 남은 가격을 앞자리부터 분배하여 최대한 큰 수를 만든다.
남은 가격을 앞자리부터 분배하여 최대한 큰 수를 만드는 방법을 모르겠어서 시작하기가 어려웠다. 어떤 자료구조를 써야 할 지부터 막혔다. 그런데 비슷한 방법으로 문제를 해결한 풀이를 발견했다.
https://www.acmicpc.net/board/view/47793
해당 풀이를 참고하여 코드를 짰다.
틀린 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static List<Price> priceList, ansList;
static StringBuilder ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
//priceList에 (가격, 숫자)쌍 추가
priceList = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
priceList.add(new Price(Integer.parseInt(st.nextToken()), i));
}
M = Integer.parseInt(br.readLine());
//가격순 정렬
Collections.sort(priceList);
//ans가 최대 50자리까지 나올 수 있으므로 정수형이 아니라 String으로 선언
ans = new StringBuilder();
ansList = new ArrayList<>();
if(N == 1){
ans.append(0);
}else {
setRoomNumber();
}
bw.write(ans+" ");
bw.close();
}
static void setRoomNumber(){
//자릿수를 최대로 만듦
//1~N 중 가장 싼 숫자 = 첫 번째 자리
if(M > priceList.get(0).price){
if(priceList.get(0).num == 0){ //가장 싼 숫자가 0이면 그 다음 싼 숫자로
M -= priceList.get(1).price;
ansList.add(new Price(priceList.get(1).price, priceList.get(1).num));
}else{
M -= priceList.get(0).price;
ansList.add(new Price(priceList.get(0).price, priceList.get(0).num));
}
//0~N 중 가장 싼 숫자 = 나머지 자리
while(true){
if(M >= priceList.get(0).price){
M -= priceList.get(0).price;
ansList.add(new Price(priceList.get(0).price, 0));
}else break;
}
//남은 돈으로 앞자리부터 큰 수로 교체
//(남은 돈 >= N가격-현재가격) 이면 바꿀 수 있음
//단, 현재 num 보다 큰 경우에만 N으로 바꾸기
for(int i=0; i<ansList.size(); i++){
for(int j=0; j<N; j++){
if(M >= priceList.get(j).price - ansList.get(i).price
&& priceList.get(j).num > ansList.get(i).num){
M -= priceList.get(j).price - ansList.get(i).price;
ansList.set(i, priceList.get(j));
}
}
}
for(int i=0; i<ansList.size(); i++){
String val = ansList.get(i).num + "";
ans.append(val);
}
}else{
//M으로 0밖에 못 만듦
ans.append(0);
}
}
}
class Price implements Comparable<Price>{
int price, num;
Price(int price, int num){
this.price = price;
this.num = num;
}
public int compareTo(Price p){
return this.price - p.price;
}
}
그러나 이 코드는 문제의 예제와 질문 게시판의 모든 반례는 통과되었지만 오답처리되었다.
아래 부분을 고려하지 못 했기 때문이다.
변경 부분
코드 설명 :
- setRoomNumber()에서 조건문 (M > priceList.get(0).price)을 제거
- 적어도 하나의 숫자를 살 수 있는 경우만 주어지기 때문에 고려할 필요가 없었음
- ansList에 Price 객체를 추가할 때 priceList에서 가져온 객체를 그대로 넣어줬다
- 불필요하게 새로운 객체를 선언해서 추가하고 있었음
- if(priceList.get(0).num == 0)을 if(priceList.get(0).num == 0 && M >= priceList.get(1).price)로 변경
- 가장 싼 숫자가 0인 경우 두 번째로 싼 숫자를 살 때, 두 번째로 싼 숫자의 가격이 M보다 작은지 검사하는 부분이 없었음
- 남은 가격 내에서 가장 싼 숫자를 최대한으로 사는 부분의 코드를 더 간단하게 변경
//변경 전
while(true){
if(M >= priceList.get(0).price){
M -= priceList.get(0).price;
ansList.add(new Price(priceList.get(0).price, 0));
}else break;
} //변경 후
while(M >= priceList.get(0).price){
M -= priceList.get(0).price;
ansList.add(priceList.get(0));
}- 남은 돈을 가지고 더 큰 숫자로 바꿀 때, priceList를 역순으로 탐색하도록 변경함
- priceList를 역순으로 탐색해야하는 이유?
- priceList에 (가격, 숫자)를 넣을 때 애초에 숫자가 오름차순으로 저장되기 때문에 따로 정렬 조건을 추가하지 않아도 Collections.sort(priceList)정렬 결과 같은 가격인 경우 숫자가 오름차순 정렬되어있다. (운 좋게 걸렸는데 아닌 경우 따로 Price클래스에 정렬 조건을 설정해줬어야 함)
- 따라서 priceList를 역순으로 탐색하면 가장 큰 숫자부터 살 수 있는지 확인할 수 있다. 그러면 가장 먼저 발견한 숫자가 구매 가능한 최대 숫자가 된다.
- 구매 가능한 최대 숫자를 발견하여 ansList의 숫자가 교체되었으면 더 탐색할 필요가 없으므로 break하여 바로 다음 숫자를 탐색하게 했다.
- (반례) priceList를 순방향으로 탐색하는 경우 오답이 나오는 TC
- priceList를 역순으로 탐색해야하는 이유?
10
1 1 1 1 1 1 1 1 1 1
50
99999999999999999999999999999999999999999999999999 //정답
21111111111111111111111111111111111111111111111111 //출력값- 이 테케의 경우 priceList 정렬 결과 (1, 0) (1, 1) (1, 2) (1, 3) … (1, 9)가 저장되어있을 것이다.
- 가장 싼 숫자로만 구성한 ansList값은 10000000000000000000000000000000000000000000000000
- 이 값의 맨 앞자리부터 priceList에 저장된 값과 비교하여 가장 큰 수로 교체해야 한다.
- priceList를 순방향으로 탐색하면 21111111111111111111111111111111111111111111111111
- priceList를 역방향으로 탐색하면 99999999999999999999999999999999999999999999999999
정답 코드
import java.io.*;
import java.util.*;
public class boj_1082 {
static int N, M;
static List<Price> priceList, ansList;
static StringBuilder ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
//priceList에 (가격, 숫자)쌍 추가
priceList = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
priceList.add(new Price(Integer.parseInt(st.nextToken()), i));
}
M = Integer.parseInt(br.readLine());
//가격순 정렬
Collections.sort(priceList);
//ans가 최대 50자리까지 나올 수 있으므로 정수형이 아니라 String으로 선언
ans = new StringBuilder();
ansList = new ArrayList<>();
if(N == 1){
ans.append(0);
}else {
setRoomNumber();
}
bw.write(ans+" ");
bw.close();
}
static void setRoomNumber(){
//자릿수를 최대로 만듦
//1~N 중 가장 싼 숫자 = 첫 번째 자리
if(M > priceList.get(0).price){
if(priceList.get(0).num == 0 && priceList.get(1).price < M){ //가장 싼 숫자가 0이면 그 다음 싼 숫자로
M -= priceList.get(1).price;
ansList.add(new Price(priceList.get(1).price, priceList.get(1).num));
}else{
M -= priceList.get(0).price;
ansList.add(new Price(priceList.get(0).price, priceList.get(0).num));
}
if(ansList.get(0).num != 0){
//0~N 중 가장 싼 숫자 = 나머지 자리
while(true){
if(M >= priceList.get(0).price){
M -= priceList.get(0).price;
ansList.add(new Price(priceList.get(0).price, 0));
}else break;
}
//남은 돈으로 앞자리부터 큰 수로 교체
//(남은 돈 >= N가격-현재가격) 이면 바꿀 수 있음
//단, 현재 num 보다 큰 경우에만 N으로 바꾸기
for(int i=0; i<ansList.size(); i++){
for(int j=0; j<N; j++){
if(M >= priceList.get(j).price - ansList.get(i).price
&& priceList.get(j).num > ansList.get(i).num){
M -= priceList.get(j).price - ansList.get(i).price;
ansList.set(i, priceList.get(j));
}
}
}
for(int i=0; i<ansList.size(); i++){
String val = ansList.get(i).num + "";
ans.append(val);
}
}
}else{
//M으로 0밖에 못 만듦
ans.append(0);
}
}
}
class Price implements Comparable<Price>{
int price, num;
Price(int price, int num){
this.price = price;
this.num = num;
}
public int compareTo(Price p){
return this.price - p.price;
}
}
Note
- 이 문제를 구현하고 밤에 자기 위해 누웠는데 문득 동전 문제와 비슷하다는 생각이 들어 dp로 구현해보면 어떨까 생각이 들었다. 2원, 4원으로 8원을 만드는 경우를 dp로 구하는 것처럼, P0 ~ PN-1원으로 M원을 만드는 경우를 dp로 구한다.
- 원래라면 M원을 만들 수 있는 경우의 수를 저장할텐데, 이 문제에서는 각각의 경우 생성될 수 있는 최대 숫자를 저장하도록 하여 구하는 것이다. 그러나 원리는 옳으나 구현에 실패하였다.
- 다른 스터디원이 이 방법으로 구현에 성공했는데 나중에 dp로도 풀어봐야겠다.
- 다른 사람의 풀이의 도움을 받고도 이틀만에 통과되었기 때문에 복습이 필요한 문제이다. 문제의 모든 경우를 빠짐없이 고려하는 게 힘들었던 문제이다.
'BOJ' 카테고리의 다른 글
| [백준 14400번 / java] 편의점 2 (0) | 2024.08.21 |
|---|---|
| [백준 22860번 / java] 폴더 정리 (small) (0) | 2024.08.19 |
| [백준 1477번 / java] 휴게소 세우기 (2) | 2024.08.01 |
| [백준 12904번 / java] A와 B (0) | 2024.07.31 |
| [백준 2143번 / java] 두 배열의 합 (0) | 2024.07.31 |