구름톤 챌린지[JAVA] 11일 차 학습 일기

구름톤 챌린지 통증 (2)

[시행 착오]

아래 코드는 처음에 제출한 오답코드이다. 처음엔 간단한 문제겠구나 하고 풀었다가 테스트 케이스에서 오답을 만나고 내가 뭘 잘못했을까 고민해봤다. 무조건 N을 큰 수부터 빼는게 중요한것이 아니고 결국은 N==0이 되는것이 가장 중요하다는것을 깨달았다. 머리로는 대충 알겠지만 도저히 스스로 풀 수가 없었다. 슬슬 모든 문제들이 풀이를 보지 않고는 풀수가 없는 단계까지 왔다. 나의 한계를 만난것이다. 그래서 풀이를 보며 코드 한 라인, 한 라인 나아가며 뜯어본 결과 이해는 됬으나 스스로 그 풀이를 작성할 수가 없어서 참고해가며 풀었다. 배낀수준이지만 이렇게라도 하면 실력이 늘것이라고 생각한다. 

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		Integer N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine(), " ");
		Integer A = Integer.parseInt(st.nextToken());
		Integer B = Integer.parseInt(st.nextToken());
		int count = 0;
		boolean flag = true;
		while(flag) {
			if(N-B>=0) {
				N-=B;
				count++;
				flag = true;
				continue;
			} else {
				flag = false;
			}
			if(N-A>=0) {
				N-=A;
				count++;
				flag = true;
			} else {
				flag = false;
			}
		}
		if(N>0){
			count=-1;
		}
		System.out.println(N);
		System.out.println(count);
	}
}

[정답 코드]

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		Integer N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine(), " ");
		Integer A = Integer.parseInt(st.nextToken());
		Integer B = Integer.parseInt(st.nextToken());
		
		int[] dp = new int[N+1];
		
		//풀이에서는 MAX_VALUE로 초기화 했다. MAX_VALUE 가 아니라 N보다 큰값이면 다 가능하지 않을까 생각한다.
		for(int i=0;i<=N;i++) {
			dp[i] = Integer.MAX_VALUE;
		}
		dp[0] = 0;
		
		for(int i=0;i<=N;i++) {
			if(i-A>=0 && dp[i-A] != Integer.MAX_VALUE) {
				dp[i] = Math.min(dp[i], dp[i-A] + 1);
			}
			//N-A 를 했을때보다 횟수가 더 적을경우 N-B로 한것을 선택한다.
			if(i-B>=0 && dp[i-B] != Integer.MAX_VALUE) {
				dp[i] = Math.min(dp[i], dp[i-B] + 1);
			}
		}
		
		//for문 끝까지 돌렸을때 dp[N] 값이 여전히 MAX_VALUE라면 -1을 출력한다.
		System.out.println(dp[N] != Integer.MAX_VALUE ? dp[N] : -1);
	}
}