글 읽기 - 틀렸습니다...? 왜일까요

s8197 5년 전 0

문제에 나온 예제 입력부터 몇 가지 예제 입력 넣어서 확인해봤는데

정답이 제대로 출력이 되는 것 같은데

왜 제출하면 틀렸다고 나오는지 도저히 못 찾겠습니다..ㅠㅠ

어느 부분이 문제가 되는 걸까요..?

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

	static int coin[], sum[];
	static int N, K;
	static ArrayList<Integer> arr = new ArrayList<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // N가지 종류의 동전
		K = sc.nextInt(); // 동전의 합

		sum = new int[K+1];
	
		for(int i=0; i<N; i++) {
			arr.add(sc.nextInt()); // 동전의 종류
		}
		
		Collections.sort(arr);
		dp();
	}
	
	public static void dp() {
		for (int i=0; i<N; i++) {
			for (int j=arr.get(i); j<=K; j+=arr.get(i)) {
				if (sum[j] == 0 || sum[j] >= sum[j-arr.get(i)]+1) {
					sum[j] = sum[j-arr.get(i)]+1;
				}
			}
		}
		
		System.out.println(sum[K] == 0 ? -1 : sum[K]);
	}
}

djm03178 5년 전 2

2 5

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

문제

문제

출처

ICPC

틀렸습니다...? 왜일까요

s8197 5년 전 0

djm03178 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말