[백준 9095번] 1, 2, 3 더하기 - 파이썬

문제 링크:

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

9095번: 1, 2, 3 더하기

 

 

---

풀이 유형:

브루트포스 알고리즘, 백트래킹, 다이나믹 프로그래밍

 

풀이 과정:

이 문제는 다이나믹 프로그래밍(DP)으로 풀 수도 있지만 아직 개념이 잡혀있지 않아 DFS를 이용해 풀어보았다.

특정한 수(n)가 주어지면 n을 1, 2, 3만을 이용해 표현해야하고 가능한 모든 경우의 수를 도출해내는 것이 목표다.

간단하게 DFS를 이용해 풀 수 있다.

더한 값(sum)이 구하는 값(num) 보다 크다면 return, 같다면 개수(count)에 1을 추가해주면 된다. 

 

여기서 DFS 개념을 다시 살펴보자.

DFS의 특징은 재귀함수이므로 반환점이 있는 마라톤이라고 생각하면 된다.

 

START 1지점(출발티켓)	2지점(식혜)	3지점(주스)	4지점(초콜릿)
END 1지점(도착티켓)	2지점(식혜)	3지점(주스)

 

위의 표는 가상의 마라톤 경기가 있다고 해보자.

각 마라톤 선수는 START 1지점 -> 2지점 -> 3지점 -> 4지점 -> 3지점 -> 2지점 -> 1지점 순을 무조건 지나가야 한다. 

즉,  ⊃방향으로 돌아야 한다.

4지점에서 마라톤이 끝나는 것이 아닌 다시 왔던 길을 되돌아가야 하는 점이 재귀함수다.

 

풀이 코드:

# 9095번 1, 2, 3 더하기

# 테스트 케이스 개수
T = int(input())

# 결과값 표시
result = []

# dfs 메서드 함수
def dfs(num, sum):
  global count
  # 더한 값이 구하는 값보다 크다면 return
  if num < sum:
    return
  # 더한 값이 구한 값과 같다면 개수 추가
  if num == sum:
    count += 1
    return
  for i in range(1, 4):
    sum += i
    # dfs 재귀적 수행    
    dfs(num, sum)
    sum -= i

# 입력받고 DFS 메서드 수행
for _ in range(T):
  num = int(input())
  count = 0
  dfs(num, 0)
  result.append(count)

# 결과 출력
for answer in result:
  print(answer)

 

 

9095번 1, 2, 3 더하기