백준 11047 : 동전 0 - JAVA

www.acmicpc.net/problem/11047

11047번: 동전 0

이 문제를 보고 나의 해결법은

 

1. n만큼의 배열을 생성한다.

2. for문을 통해 n만큼의 배열에 값을 집어넣는다.

3. for문을 통해 n번째 부터 시작하여 n값이 감소하며 몫이 0보다 커질때를 구한다.

4. 몫이 0보다 크다면 나눌 수 있는 제일 큰값이라는 소리이므로 그 값을 몫 변수에 저장한다.

5. 이때 나오는 나머지 값을 이중 폴문을 이용하여 같은 방법으로 찾았다.

 

여기까지 했을때 1번 입력에 대한 정답은 구했지만 2번 입력에 대한 정답을 구하지 못했다.

package test;

import java.util.Scanner;

public class test {

	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int m =0;
		//n[i]로 나눌때의 몫
		int m2 =0;
		// n[j]로 나눌때의 몫
		int na =0;
		// n[i]로 나눌때의 나머지
		
		int num[] = new int[n];
		
		for(int i =0;i <n;i++) {
			num[i] = sc.nextInt();
		}
		
		for(int i =n-1; i>=0; i--) {
			if((k/num[i])>0) {
				//처음 가장 큰 수로 나눠질때의 경우
				m = k/num[i];
				// 몫을 저장 동전의 수의 일부
				na = k%num[i];
				// 나머지값 저장
				
				for(int j=i;j>=0;j--) {
					//이때의 i값부터 다시 탐색
					if(na/num[j]>0) {
						//다음 가장 큰 수로 나눠질 경우
						m2 = na/num[j];
						// 두번째 몫을 저장 
						break;
					}
				}
				break;
			}
		}
		System.out.println(m+m2);
	}
}

 

뭔가 이상함을 느꼇다.. 10원의 경우도 있어야 한다는걸 늦게 깨달았다. 그렇다면 1의자리수까지 표현하려면?

뭔가 프로그램이 복잡해 질 것 같다는 생각이 들고 다시 한번 처음으로 돌아가 생각해보기로 하였다.

 

나의 부족함을 느끼게 해주는 문제였다... 왜이래 멍청하지..

이중 for문 마저 쓸필요가 없고

 

1. num[i]가 처음으로 같거나 작을때 나눈 몫 값을 저장한다. 

2. 이때 k 값은 나머지값으로 변환시킨다.

3. 반복문이 돌고 몫 값에 몫 + 다음번의 몫 값을 더해준다.

 

이런식으로하면 for문안에서 몇줄만으로 해결이 되는 문제라는걸 알게되었다.....

package test;

import java.util.Scanner;

public class test {

	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int m = 0;
		
		int num[] = new int[n];
		
		for(int i =0;i <n;i++) {
			num[i] = sc.nextInt();
		}
		
		for(int i = n-1;i>=0;i--) {
			if(num[i] <= k) {
				m += (k/num[i]);
				k = k%num[i];
			}
		}
		System.out.println(m);
	}
}

매일매일 공부하면 좀더 발전할거라 믿고 열심히 해야겠다.