[코딩테스트] 백준 - DP문제 오답 모음(BronzeⅤ ~ SilverⅢ)

2025.04.22 ~ (추가 중)

 

✔️백준 #1463 "1로 만들기"

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

 

문제 요약

정수 N이 (1) 3의 배수면 3으로 나누기 (2) 2의 배수면 2로 나누기 (3) 1을 빼기

위와 같은 연산 세 개를 적절히 사용해서 1을 만드는 최소 연산 횟수 구하기

▫️입력: N (1 ≤ N ≤ 10^6)

▫️출력: 최소 연산 횟수

 

나의 정답

N = int(input())

# DP 배열 초기화
F = [0] * (max(4, N+2))  # 최소 크기 4 이상 확보

# 시작 상태 정의
F[1], F[2], F[3] = 0, 1, 1

# DP식 구현
for n in range(4, N+1):
    # 2의 배수면서 3의 배수인 경우
    if n % 3 == 0 and n % 2 == 0:
        F[n] = 1 + min(F[n-1], F[n//2], F[n//3])
    # 3의 배수인 경우
    elif n % 3 == 0:
        F[n] = 1 + min(F[n-1], F[n//3])
    # 2의 배수인 경우
    elif n % 2 == 0:
        F[n] = 1 + min(F[n-1], F[n//2])
    # 나머지 경우
    else:
        F[n] = 1 + F[n-1]

# 값 반환
print(F[N])

틀린 이유

나는 반복문 이용해서 바텀-업으로 풀었음

1) 2의 배수이자, 3의 배수인 케이스를 생각 못함
-> 결국엔 -1, //2, //3 중 가능한 1~3개의 경우를 모두 비교했을 때 가장 작은 값을 선택하도록 해야함!

2) DP 배열 초기화 시, F = [0] * (N+2) 같은 식으로 하는 경우엔, N=1인 경우엔 F[3]이 정의되지 못하여 인덱스 에러 발생

---

✔️백준 #9095 "1, 2, 3 더하기"

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

 

문제 요약

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

▫️입력: 첫째 줄에 테스트 케이스의 개수 T, 이후에는 테스트 케이스 개수만큼 정수 n이 주어진다. (0 < n < 11)

▫️출력: 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수 출력

 

나의 정답

tc = int(input())
for _ in range(tc):
    N = int(input())
    F = [0] * max(4, N + 1)  # DP 배열 초기화
    F[1], F[2], F[3] = 1, 2, 4  # 시작 상태 정의

    for n in range(4, N+1):
        F[n] = sum([F[i] for i in range(n-3, n)])

    print(F[N])

 

틀린 이유  
문제는 굉장히 쉬웠으나, 마음이 급해서 올바른 규칙을 못찾았다! ...
앞으로는 귀찮더라도 차분히 손으로 작성해보고 확실한 DP식을 세우는 연습이 더 필요할 것 같다

---

✔️백준 #2579 "계단 오르기"

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

 

문제 요약

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성 하시오.

▫️조건

▪️계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.

▪️ 연속된 세 개의 계단을 모두 밟아서는 안 된다. (단, 시작점은 계단에 포함 X)

▪️ 마지막 도착 계단은 반드시 밟아야 한다.

▫️입력: 첫째 줄에 계단의 개수 N, 이후에는 각 계단에 쓰여 있는 점수 S가 차례대로 주어진다. (1  ≤ N ≤ 300, 1  ≤ S ≤ 10,000)

▫️출력: 얻을 수 있는 총 점수의 최댓값 출력

 

나의 정답

N = int(input())
scores = list(map(int, input().split()))

# 0 <= N < 3인 경우 예외 처리
if N == 0:
    print(0)
elif N == 1:
    print(scores[0])
elif N == 2:
    print(scores[0] + scores[1])
else:
    # DP 배열 초기화
    # F[a][b] : a 계단까지 (b+1)칸 이동
    F = [[0] * 2 for _ in range(N+1)]  # (N+1) x 2
        
    # 시작 상태 정의
    F[1][0] = scores[0]
    F[2][0] = scores[1] + F[1][0]
    F[2][1] = scores[1]

    for i in range(2, N):
        F[i+1][0] = scores[i] + F[i][1]  # 1칸 연속
        F[i+1][1] = scores[i] + max(F[i-1][0], F[i-1][1])  # 2칸 점프

    print(max(F[N][0], F[N][1]))

 

틀린 이유

(1) 계단 개수가 3개 이하인 경우 고려 못함 → 예외 처리 추가

(2) 자꾸 3%대에서 IndexError가 100번은 발생함..

파이참으로 가능한 모든 반례를 다 넣어봤을 때는 제대로 정답이 나오는데 ㅠㅠ 이유를 몰라서 답답해 죽을 뻔했다..

하다하다 chatGPT에 인덱스에러 원인 물어봐도 이상한 소리만 하고.. 진심 2시간 동안 별 짓 다했는데 모르겠음

---

✔️백준 #11726 "2×n 타일링"

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

 

문제 요약

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

입력: n (1 ≤ n ≤ 1,000)

출력: 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력

 

나의 정답

N = int(input())

F = [0] * max(3, (N + 1))  # DP 배열 초기화
F[0], F[1], F[2] = 0, 1, 2  # 시작 상태 정의

# Bottom-up Method
if N >= 3:
    for i in range(3, N+1):
        F[i] = F[i-1] + F[i-2]
print(F[N] % 10007)

 

풀이 과정

그림 그려서 규칙을 찾아보니까 피보나치와 동일했음!

인덱스 에러가 한 번 났는데, 초기 상태 정의 시 N이 2보다 작은 경우에 문제가 발생할 수 있음

항상 꼼꼼하게 체크해야겠다는 걸 다시 한 번 깨달았다