[백준 14568번] 2017 연세대학교 프로그래밍 경시대회

문제

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

 

풀이

- 완전 탐색 풀이

N = int(input())

answer = 0
for a in range(1, N + 1):
    for b in range(1, N + 1):
        for c in range(1, N + 1):
            if a + b + c == N:
                if c >= b + 2:
                    if a != 0 and b != 0 and c != 0:
                        if a % 2 != 1:
                            answer += 1

print(answer)

모든 조건을 명시해서 풀어준다.

시간복잡도: O(N³)

 

- 최적화

n = int(input())

result = 0
for i in range(2, n - 2, 2):
    result += (n - i - 2) // 2
print(result)

택희가 받는 사탕을 i개로 하고

n개의 사탕에서 택희 사탕 i, 남규가 더 받을 사탕 2개를 빼주고 // 2를 하면

조건을 만족하는 조합의 수를 구할 수 있다.

시간복잡도: O(N)