[DP]문제#5. 등굣길

코딩테스트 연습 - 등굣길 | 프로그래머스 (programmers.co.kr)

​

이 문제는 따져야할 조건이 많다

​

1. 만약 물웅덩이가 테두리 부분에 있을 경우

ex) m=4, n=3 인데 물웅덩이가 (1,2)에있으면 (1,3), (1,3) 도 이동할수 없다.

​

2. 주어진 puddles[][]에서

puddles[행][열] (x) puddles[열][행] (o)

​

3. 경로의 개수를 구하는 과정에서도 계산된 값에 %1000000007 을 해주어야한다.

결과값에만 처리하면 안된다

​

이 조건들을 꼼꼼히 따져가며 풀어야할 문제이다.

 

import java.util.Scanner;

//동전2
public class Main {

	static int n;
	static int k;
	static int[] money;
	static int[] d;
	static int coin;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		n=in.nextInt();	
		k=in.nextInt();	
		
		money=new int[n];
		d=new int[k+1];
		

		for(int i=0;i<n;i++) {
			money[i]=in.nextInt();
		}
		d[0]=0;
		for(int i=0;i<n;i++) {
			coin=money[i];
			for(int j=coin;j<=k;j++) {
				if(j==coin) d[j]=1;
				
				if(d[j-coin]==0) continue;
				else {
					if(d[j]!=0) d[j]=Math.min(d[j], d[j-coin]+1);
					else if(d[j]==0) d[j]= d[j-coin]+1;
				}
				
			}
		}
		if(d[k]==0) System.out.println(-1);
		else System.out.println(d[k]);
	}

}