Q 14568 2017 연세대학교 프로그래밍 경시대회

💡 문제 요약 및 분석

택희, 남규, 영훈이가 N 개의 사탕을 나눠 가지는 방법의 가짓수를 구해내면 된다. (규칙을 만족하는 방법이 없다면 0을 출력한다.)

- 남는 사탕은 없어야 한다.
- 남규는 영훈이보다 2개 이상 많은 사탕을 가져야 한다.
- 셋 중 사탕을 0개 받는 사람은 없어야 한다.
- 택희가 받는 사탕의 수는 홀수개가 되어서는 안 된다.

💡 알고리즘 설계

문제에서 제시한 규칙을 바탕으로 아래와 같이 조건문을 만들어보았다.

1. 택희가 2의 배수로 가져가야 한다. a = 2, 4, 6 ...

2. 전체 사탕 N 개에서 택희가 가져간 사탕을 뺀 나머지 사탕 M 개가 3개 이상이어야 조건대로 나눠가질 수 있다.

3. 남규 사탕을 b = 1, 2, 3 ... 으로 반복문을 돌리면서 (M - b) >= (b + 2) 조건을 만족시키면 전체 규칙을 만족하게 되므로 count++ 한다.

💡 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        br.close();

        int count = 0;
        for (int a = 2; a < n; a+=2) { // 조건 1
            int m = n - a;
            if (m < 3) { // 조건 2
                break;
            }
            for (int b = 1; b < m; b++) {
                if (m - b >= b + 2) { // 조건 3
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

💡 틀린 부분 수정

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n^2)	O(1)

• ⏱️ 중첩된 반복문이 있어서 반복 횟수가 곱해진다. (외부 루프 = n/2 번, 내부 루프 = (n-a)/2 번 반복한다. 일반화하면 n^2 이 된다.)

💡 다른 풀이

규칙이 명확하게 주어진 문제라서 설계 방식도 다들 비슷한 것 같다. 다만 구현하는 방식에서 조금 다른 풀이가 있어서 가져와봤다.

int N = Integer.parseInt(br.readLine());
int count = 0;

for (int A = 1; A < N; A++) {
    // 택희가 짝수 개를 가져가야하므로 조건문으로 처리한다.
    if (A % 2 != 0) continue;

    for (int B = 1; B < N - A; B++) { 
        // '남은 사탕 - 남규가 가져간 사탕 = 영훈이 사탕 = C'이다. 아래와 같이 분기 처리한다.
        int C = N - A - B;
        if (C <= 0) continue;
        if (C >= B + 2) {
            count++;
        }
    }
}