글 읽기 - Map 으로 풀면 안되는 이유 아시는 분 계신가요?ㅠㅠ

cds06126 2년 전 1

제 생각엔 똑같은 로직인데,

Map을 사용한 코드는 18프로에서 틀리내요 ㅠㅠ

무슨 이유 때문일까요??ㅠㅠ제 생각엔 똑같은 로직인데,

Map을 사용한 코드는 18프로에서 틀리내요 ㅠㅠ

무슨 이유 때문일까요??ㅠㅠ

import java.util.*;
import java.io.*;


class Main{
	
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		int k = Integer.parseInt(bf.readLine());
		
		int[] coins = new int[k+1];	coins[0] = 0;
		TreeMap<Integer, Integer> cc = new TreeMap<>();
		for(int c = 1; c<=k; c++){
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int coin = Integer.parseInt(st.nextToken());
			int count = Integer.parseInt(st.nextToken());
			coins[c] = coin;
			cc.put(coin, count);
		}
		Arrays.sort(coins);
		//
		long[][] dp = new long[k+1][T+1];
		for(int i = 0; i<=k; i++)	dp[i][0] = 1L;
		for(int i = 1; i<=k; i++){
			int coin = coins[i];
			int count = cc.get(coin);
			for(int j = 1; j<=T; j++){
				for(int c = 0; c<=count && coin * c <=j; c++){
					dp[i][j] += dp[i-1][j-coin * c];
				}
			}
		}
		System.out.println(dp[k][T]);	
	}
}
//이상 틀리는 코드
=======================VS=========================
//이하 맞는 코드
import java.util.*;
import java.io.*;


class Main{
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		int k = Integer.parseInt(bf.readLine());
		
		Coin[] coins = new Coin[k+1];	coins[0] = new Coin(0, 0);
		for(int c = 1; c<=k; c++){
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int coin = Integer.parseInt(st.nextToken());
			int count = Integer.parseInt(st.nextToken());
			coins[c] = new Coin(coin, count);
		}
		Arrays.sort(coins);
		// END OF INIT
		long[][] dp = new long[k+1][T+1];
		for(int i = 0; i<=k; i++)	dp[i][0] = 1L;
		for(int i = 1; i<=k; i++){
			int coin = coins[i].coin;
			int count = coins[i].count;
			for(int j = 1; j<=T; j++){
				for(int c = 0; c<=count && coin * c <=j; c++){
					dp[i][j] += dp[i-1][j-coin * c];
				}
			}
		}
		System.out.println(dp[k][T]);	
	}
}

class Coin implements Comparable<Coin>{
	int coin, count;
	Coin(int c, int c2){this.coin = c;	this.count = c2;}
	@Override
	public int compareTo(Coin o){
		return this.coin - o.coin;
	}
}  

djm03178 2년 전 1

값어치가 같은 동전이 여러 종류일 때 기존의 내용을 덮어쓰게 됩니다.

cds06126 2년 전 0

@djm03178 물론 문제에서 모든 동전의 값어치가 다르다곤 안했지만,,, 당연히 다를거라고,, 아니 굳이 같은 값어치의 동전이 있을 거라곤 생각을 안했네요,,ㅎㅎㅎ

친절한 답변 정말 감사합니다~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Map 으로 풀면 안되는 이유 아시는 분 계신가요?ㅠㅠ

cds06126 2년 전 1

djm03178 2년 전 1

cds06126 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말