[코드트리/NOVICE MID] 수를 여러번 사용하여 특정 수 만들기 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine() , " ");
 
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
 
        int answer = Integer.MIN_VALUE;
 
        for(int i = 0 ; i <= C / A ; i++) {
            for(int j = 0 ; j <= C / B ; j++) {
                int tmp = A * i + B * j;
 
                if(tmp <= C) {
                    answer = Math.max(answer, tmp);
                }
            }
        }
 
        System.out.println(answer);
    }
}

 

 

🧩  해결 아이디어

• 완전탐색

.A를 0번부터 C / A번 사용하고, B를 0번부터 C / B번 사용해 숫자를 만든다.

만든 숫자가 C보다 작거나 같다면, 현재 최댓값과 비교해 갱신한다.

 

 

 

---

🔺 다른 풀이들

- A의 사용횟수에 따라 최대 사용 가능한 B의 개수를 구하고, 그에 따른 합의 최댓값을 구한다.

import java.util.Scanner;
 
public class Main {
    public static int a, b, c;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
 
        int ans = 0;
 
        for(int i = 0; i * a <= c; i++) {
            int cnt = a * i;
 
            int numB = (c - cnt) / b;
 
            cnt += numB * b;
            
            ans = Math.max(ans, cnt);
        }
 
        System.out.print(ans);
    }
}

 

 

---

💬 느낀 점

길고 어려운 문제를 풀 때가 된 것 같다..

 

1회독	2회독	3회독	4회독	5회독
V