[JAVA] 14916번 - 거스름돈

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

그리디 알고리즘문제이다. 

 

첫번째 시도 (틀림)

거스름돈 액수 / 5 = 몫A, 나머지B

나머지B / 2 = 몫C, 나머지D

나머지가 0으로 떨어지지 않는다면 -1을출력한다.

몫A+몫C더하면 된다 

 

두번째 시도 (틀림)

5로 나누고 나머지를 가지고 0,1,2,3,4일경우에 따라 다르게 계산

 

세번째 시도 (맞춤)

두번정도 틀리고 나서 무작정 5를 나누면 안된다고 생각했다.

13의 경우 5원이 1개가 필요한데 무작정 5를 나누면 여기서부터 오답이기 때문

그래서 반대로 2원을 먼저 계산하는 방법으로 접근했다

1. 5의 배수면 그냥 몫을 출력하면 끝

2. 5의 배수가 아닐 경우는 5의 배수가 될때까지 2를 뺴주면서 2를 뺄때마다 카운트를 한다

    5의 배수가 되면 1의 경우처럼 나눠서 몫을 구하고

    몫+cnt 출력을 한다 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1.while문으로 5의 배수가 될때까지 돌린다.

2-1. 5의 배수일경우 바로 몫을 출력한다

2-2. 5의 배수가 아닐경우 5의 배수가 될때까지 2를 빼주면서 빼준 횟수를 카운팅한다

3. num이 안떨어질경우 -1출력, 그게 아니라면  카운팅횟수+5로 나눈 몫 출력

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

첫번째 시도

=> 기존 거스름돈 문제 처럼 풀고 있었다

public class Main {
	static int arr[][] = new int[5][5];  
	static int ans = 0;
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int num = Integer.parseInt(br.readLine());
		int n[] = {5,2};
		int sum=0;
	
		
		for(int i=0; i<n.length; i++) {
			int a =num/n[i];
			sum+=a;
			num=num%n[i];
		}
		System.out.println(sum);
	}
}

 

두번째 시도

=> 이렇게 계산을 해버리면 13의 경우는 5가 1이 되어야하는데 무조건 2가 되기떄문에 안됨

두번 틀리고 나니까 무작정 5를 나누면 안된다는 판단이 들었다 

public class Main {
	static int arr[][] = new int[5][5];  
	static int ans = 0;
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int num = Integer.parseInt(br.readLine());
		int sum=0;
	
		int a=num/5; 
		int b=num%5;
		
		if(b==1 ) {
			System.out.println(-1);
		}
		else if(b==0) {
			System.out.println(a);
		}
		else if(b==4){
			System.out.println(a+(b/2));
		}
		else if(b==2) {
			System.out.println(a+1);
		}
		else {
			
		}
	
	}
}

 

 

정답코드

public class Main {
	static int arr[][] = new int[5][5];  
	static int ans = 0;
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int num = Integer.parseInt(br.readLine());
		int sum=0;
		int cnt=0;
	
		while(num % 5 != 0) {
			if(num%5==0) {
				System.out.println(num/5);
				return;
			}
			else {
				num-=2;
				cnt++;
			}
 		}
		if(num<0) {
			System.out.println(-1);
		}
		else {
			System.out.println(cnt+(num/5));
		}