구름톤 챌린지 11일차 - 통증 (2)

https://level.goorm.io/exam/195693/%ED%86%B5%EC%A6%9D-2/quiz/1

구름LEVEL

import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		int answer = -1;
		int[] array = new int[N/A+1];
		
		for(int i=0; i<array.length; i++){
			int number = N - (A * i);
			array[i] = number / B;
			if(number % B == 0){
				answer = array[i] + i;
				break;
			}
		}
		
		System.out.println(answer);
	}
	

	

}

처음에 풀었던 방식이 너무 오래걸리고 생각보다 답을 찾아내지 못해서 처음부터 다시 시작했다.

이 문제는 지난 8일차와 비슷하지만 그리드로 풀리지 않는 문제이다. 문제 설명에 적혀있다 싶이 다이나믹 프로그래밍(동적 계획법)으로 풀어야했다.

 

내가 생각한 답안이 나올 경우의 수는 

1) N이 B로 나눠지는 경우

2) N이 B로 나누어지지 않아 A를 하나씩 빼주었을 때 B로 나눠지는 경우

3) 그렇게 해서도 답이 나오지 않는 경우

 

N = A * x + B * y;

answer = x + y;

y = (N - A * x)/B;

x -> i로 y -> array[i]로

 

그래서 배열을 하나 만들어서 A를 한 번씩 빼면서 N이 B로 나눠지는지 확인하였다.

여기서 문제는 배열의 크기를 어떻게 잡는가였는데, 이는 배열이 가장 큰 경우가 N이 A로 나눠지는 경우이기 때문에 N/A+1로 잡았다.

answer를 -1로 잡고, 만약 A와 B로 나누어지는 경우를 찾았을 때 answer를 바꾸도록 구현하였다.