[백준] no9095: 1,2,3더하기

문제

주어진 숫자를 1과 2와 3의 합으로 구할 수 있는 경우의 수를 모두 구하시오

단, 순서가 다르면 다른 케이스로 취급함

예를 들어 4가 되기 위해서 1 + 3과 3 + 1은 각각 다른 케이스로 취급

 

문제 링크 : https://www.acmicpc.net/problem/9095

---

원리

필자는 BFS로 풀이했다.

---

풀이방법

1. 여러 케이스를 나타내기 위해 BufferedWriter를 사용했다.

2. BFS로 1,2,3를 더해주는 경우를 반복하기 위해 static int[]로 1,2,3을 넣어줌

3. BFS를 static메소드로 돌리기 위해 입력값을 static int에 할당해줌

4. 1과 2와 3의 경우, 초기값으로 넣어주기 때문에 엣지케이스를 따로 처리해줌(그래야 처리속도가 더 빠름)

5. 그 외엔 BFS메소드로 처리

6. BFS를 위해 대기열을 만들어줌. 이때 일반 Queue보단 Deque가 처리속도가 더 빠름(ArrayDeque사용)

7. 경우의 수를 세어줄 count를 선언하고, 대기열에 초기값인 1,2,3을 넣어줌

8. 이제 대기열에 있는 요소들에대해 반복을 시작함.(더이상 대기열에 남는 경우가 없을때까지)

9. 2번에 선언해둔 static배열을 순차적으로 더해주며,

    작으면 다시 대기열로

    같으면 count+1

    크면 무시

10. 대기열이 비어서 반복이 종료되면, 총 세아린 숫자를 반환하여 BufferedWriter에 입력

---

나의 코드

static int goal;
static int[] arr = {1,2,3};

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int T = Integer.parseInt(br.readLine());

    for(int i=0; i<T ; i++) {
        goal = Integer.parseInt(br.readLine());
        if(goal==1) bw.write("1\n");
        else if(goal==2) bw.write("2\n");
        else if(goal==3) bw.write("4\n");
        else bw.write(""+BFS()+"\n");
    }

    bw.close();
}

public static int BFS() {
    Deque<Integer> dq = new ArrayDeque<>();
    int count = 0;
    dq.add(1);
    dq.add(2);
    dq.add(3);

    while(!dq.isEmpty()) {
        int now = dq.poll();

        for(int i=0; i<3 ; i++) {
            int isPossible = now + arr[i];
            if(isPossible<goal) dq.add(isPossible);
            else if (isPossible==goal) count++;
        }
    }
    return count;
}