자료구조&알고리즘/알고리즘 - 대회 알고리즘

[알고리즘 문제 풀이][DP] 백준 9184번 - 신나는 함수 실행

초코쨔응 2024. 12. 25. 18:59

반례가 많이 발생하는 문제였기에 기록 필요

 

- 문제 설명: https://www.acmicpc.net/problem/9184

재귀함수 w(a,b,c) 를 재귀함수를 사용하지 않고, 아래에 조건에 맞게 출력되도록 구현하라는 문제입니다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

 

 

- 문제 풀이:

재귀를 사용하지 않는다면 합을 계산하기 위해 DP 를 이용할 수 있습니다.

 

a, b, c가 하나라도 20을 넘는 경우는 모두 w(20,20,20) 으로 같은 결과가 나오기 때문에, w(20,20,20) 의 결과값까지만 구현하면 됩니다.

또한 a, b, c 중 하나라도 0 이하인 경우에는 답이 1이기 때문에 w(0,0,0) 부터의 값만 구하면 됩니다.

따라서 3중 포문을 이용하여

for (i = 0 ~ 20)

  for (j = 0 ~ 20)

    for (k = 0 ~ 20)

을 순회해서 구하면 됩니다.

 

 

- 코드 (Python): 

아래는 Python 을 이용한 코드 예시입니다.

문제에서 주어진 조건식 대로 DP 배열을 채워나가고 있습니다.

그리고 들어온 입력값을 조건에 맞게 확인하여 결과를 출력합니다. (0 과 20 체크)

DP = [[[0 for i in range(21)] for j in range(21)] for k in range(21)]
for i in range(21):
    for j in range(21):
        for k in range(21):
            if i <= 0 or j <= 0 or k <= 0:
                DP[i][j][k] = 1
            elif i < j and j < k:
                DP[i][j][k] = DP[i][j][k-1] + DP[i][j-1][k-1] - DP[i][j-1][k]
            else:
                DP[i][j][k] = DP[i-1][j][k] + DP[i-1][j-1][k] + DP[i-1][j][k-1] - DP[i-1][j-1][k-1]
while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    if a <= 0 or b <= 0 or c <= 0:
        a2, b2, c2 = 0, 0, 0
    elif a > 20 or b > 20 or c > 20:
        a2, b2, c2 = 20, 20, 20
    else:
        a2, b2, c2 = a, b, c
    print(f"w({a}, {b}, {c}) = {DP[a2][b2][c2]}")

 

- 실수 포인트 & 반례:

1. 조건문의 순서가 반대로 된 경우,
a, b, c가 하나라도 0 보다 작은 경우가 순서가 더 먼저여야하는데, 20 초과를 먼저 확인하는 경우 답을 틀리게 됩니다.
(3% 대에서 틀립니다.)
 
입력
-9 33 -5
8 20 6
38 -12 -45
-1 -1 -1

출력
w(20, 20, 20) = 1048576
w(8, 20, 6) = 256
w(20, 20, 20) = 1048576

정답
w(-9, 33, -5) = 1
w(8, 20, 6) = 256
w(38, -12, -45) = 1
 
 
2. C 언어의 경우 음수 처리를 하지 않는 경우
 
3. 틀린 대부분의 많은 경우가 출력 형식을 맞추지 않은 경우
- w를 대문자로 쓰거나
- 띄어쓰기를 틀리거나
- 입력마다 엔터가 들어오지 않거나
- w(a, b, c) = d 가 아닌 d 만 출력하거나
반응형