[백준] 15989번. 1, 2, 3 더하기 4(JAVA)

문제

https://www.acmicpc.net/problem/15989

---

풀이(22분)

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

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 n = Integer.parseInt(st.nextToken());

        for(int i = 0; i < n; i++){
            System.out.println(check(Integer.parseInt(br.readLine())));
        }
    }

    public static int check(int x){
        if(x <= 3){
            return x;
        }
        int count = 0;

        // 중복 허용 조합 생성
        for (int c = 0; c <= x / 3; c++) { // c는 3의 개수
            for (int b = 0; b <= (x - 3 * c) / 2; b++) { // b는 2의 개수
                int a = x - 3 * c - 2 * b; // a는 1의 개수
                if (a >= 0) {
                    count++;
                }
            }
        }

        return count;

    }

}

 

처음엔 이전의 1,2,3 더하기 문제처럼 dp를 생각했다. 하지만 n=10000까지라는 제한이 있는 문제에 이렇게 접근해도 되지 않을까 했다.

내가 이용한 것은 a + 2b + 3c = x의 부정방정식을 푸는 것이다.(중고딩 때 많이 풀었던 문제!!)

 

대략 c= 0일 때 b = x/2 정도의 연산을 가진다. 즉 최대 10000이어도 5000번의 연산으로 끝난다는 소리다.

그럼 c = 0 ~ 3333까지 갈 때 b는 계속 줄어든만큼의 연산만 수행하면 된다.

하지만 대충 말도 안 되게 계산해봐도 5000x3333 = 15,000,000의 연산이면 끝난다는 것을 알 수 있다.

 

즉!!! 너무 어렵게 생각하지 않고 그냥 풀어도 되는 문제다!!