글 읽기 - 1049 기타 줄 예외 케이스가 또 있나요?

cherrimy 5년 전 0

동전 교환 처럼 문제를 풀어보려고했는데,

몇가지 샘플로 확인했는데.... 반례를 찾기가 힘들어서요

package Greedy;

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

public class Q_1049 {

	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 = new StringTokenizer(br.readLine().trim());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int []oneV = new int[m+1];
		int []sixV = new int[m+1];
		int d[] = new int[n+1];
		
		for (int i = 1; i <=m ; i++) {
			st = new StringTokenizer(br.readLine().trim());
			sixV[i] = Integer.parseInt(st.nextToken());
			oneV[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 1; i <=n; i++) {
			d[i] = Integer.MAX_VALUE/2;
		}
		
		for (int i = 1; i <=n; i++) {
			if (i - 1 >= 0) {
				for (int j = 1; j <=m; j++) {
					d[i] = Math.min(d[i], d[i-1] + oneV[j]);
				}
			}
			
			if (i - 6 >= 0) {
				for (int j = 1; j <=m; j++) {
					d[i] = Math.min(d[i], d[i-6] + sixV[j]);
				}
			}
		}
		
		System.out.println(d[n]);
	}

}

cherrimy 5년 전 0

7 2

15 3

12 4

=> 15

8 2

12 1

15 27

=> 8

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

문제

문제

출처

ICPC

1049 기타 줄 예외 케이스가 또 있나요?

cherrimy 5년 전 0

cherrimy 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말