구름톤 챌린지 11일차

문제

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

구름LEVEL

 

풀이

DP 문제라고 되어있었는데 DP 문제라고 하기에는 뭔가 아닌듯한 느낌이었다.

0이 될려면 a의 곱과 b의 곱을 더한 것이 n이 되어야 한다.

즉, n/b의 최대 몫을 구한다음 1씩 빼가면서 n의 나머지값을 구한다.

나머지 값을 a로 나누어 떨어졌을 때에는 그것이 답이 된다

 

코드

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
	int answer  = -1;

		for(int i=n/b;i>=0;i--){
			if((n - i*b)%a == 0){
				answer = i + (n - i*b)/a;
				break;
			}
		}
		
		System.out.println(answer);
	}
	
}