[코딩테스트] 백준(BAEKJOON) - 동전 1(Java, 2293번)

안녕하세요.

오늘 기록해놓을 코딩테스트 문제는 바로 동전 1입니다.

 

요즘 너무 바쁘네요~ 운전면허딴지 3달이 돼서 글을 올리고자하는데 찔끔찔끔쓰며 진행을 못하고 있습니다. ㅠㅠ

 

역시 어려웠습니다. ㅠㅠ

해당 문제 먼저 설명드리고 제가 생각했던부분과 실제다른 부분을 살짝 남겨놓고자 합니다.

https://www.acmicpc.net/problem/2293

2293번: 동전 1

문제만 보면 오쉬운데?라는 생각이 들었으나!

제가 틀렸음을 한5분정도 고민하다 알았습니다.

 

제가 작성한 코드를 보여드리며 제가 풀려그랬던 생각과 실제 답에 대한 설명을 진행 하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
			
			String line=bf.readLine();
			int n=Integer.parseInt(line.split(" ")[0]);
			int k=Integer.parseInt(line.split(" ")[1]);
			int[][]dp=new int[n+1][k+1];
			
			for(int i=1;i<=n;i++)
			{
				int number=Integer.parseInt(bf.readLine());
				for(int j=1;j<=k;j++)
				{
					if(number==j)
						dp[i][j]=dp[i-1][j]+1;
					else
					{
						if(j<=number)
							dp[i][j]=dp[i-1][j];
						else
							dp[i][j]=dp[i][j-number]+dp[i-1][j];
					}
						
				}
				
			}
			System.out.println(dp[n][k]);
	}

}

먼저, 제 생각을 기록하겠습니다.

저는  dp 테이블 하나를 만들며~  만약 4라면 반복문을 통해

3개와 1개의 조합일 경우

+ 2개와 2개의 조합일 경우

+ 1개와 3개의 조합일 경우

+ 0개와 4개의 조합일 경우 이런식으로 무식하게 풀 수 있을거라 생각했습니다. ㅠㅠ

 

접근도 틀렸지만 이번 문제의 핵심은 중복되지 않는데 있다고 생각합니다.

1일때는 1~10까지 만들 수 있는 경우의 수가 (1=>1), (2->1,1), (3=>1,1,1) 이런식으로 1가지의 경우밖에 없습니다.

그럼 다음 2부터는 어떨까요?

 

◎ 2로는 2보다 작은 수 1을 만들 수 없습니다. 그렇기에 첫 번째 줄의 값을 그대로 가져오겠습니다.

◎ 또한 2일때는 기존의 첫 번째 줄에서 계산한 경우의 수에 2=>1,1에서 2 하나만 추가됐으므로 +1을 해주겠습니다.

◎ 나머지 경우는 사실 왜 그런지 논리적으로는 저도 계속 공부중이나... 다들 뭐 규칙성이 보인다라고합니다..

그리고 윗 줄 값 + 진행중인 줄-2번째의 값을 더하면 된다고합니다.

 

해당 부분은 공부후에 다시 수정해야겠습니다.

 

알쏭달쏭 DP네요 정말...🤔

 

정말 찜찜하게 동전1 문제를 마무리일단 하겠습니다.

 

감사합니다. :D