728x90
풀이 1: DP
이 문제를 위한 가장 효율적인 방법은 DP를 사용하는 것이다.
초기값
초기값 dp[1] = 1, dp[2] = 2, dp[3] = 4
(dp[2]는 1+1, 2로 2가지, p[3]은 1+1+1, 1+2, 2+1, 3으로 4가지)
점화식
4일 때 dp[3]+1, dp[2]+2, dp[1]+3와 같이 구할 수 있다.
--> n은 dp[n-1]+3, dp[n-2]+2, dp[n-3]+3
--> 방법의 수 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
1, 2, 3의 합으로 나타내는 방법의 수에서 한 번 계산한 값을 재사용함으로써 중복 계산을 방지하고, 시간 복잡도를 줄일 수 있다.
def count_ways(n):
# n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 저장할 dp 배열 초기화
dp = [0] * (max(4, n+1)) # n이 3 이하일 경우를 대비하여 최소 크기는 4로 설정
dp[0], dp[1], dp[2], dp[3] = 0, 1, 2, 4 # 초기값 설정
# 4부터 n까지의 각 숫자에 대해 계산
# n이 3 이하인 경우에는 아래의 for 루프 실행되지 않음.
for i in range(4, n+1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
return dp[n]
# 메인 실행부
T = int(input())
results = []
for _ in range(T):
n = int(input())
results.append(count_ways(n))
for result in results:
print(result)dp[i]는 i를 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 저장한다.
초기값으로 dp[1], dp[2], dp[3]를 설정한 다음, 각 숫자를 1, 2, 3의 조합으로 만들 수 있는 방법의 수를 순차적으로 계산한다.
아래와 같이 for문에서 range를 활용해 특정 범위에서는 실행이 되지 않도록 하는 것 잘 활용하자 !
# n이 3 이하인 경우에는 아래의 for 루프 실행되지 않음.
# (3 이하인 경우에는 미리 설정한 초기값을 리턴하게 됨)
for i in range(4, n+1):
풀이 2: 재귀 함수 이용
def count_ways(n):
if n < 0:
return 0
elif n == 0:
return 1
else:
return count_ways(n-1) + count_ways(n-2) + count_ways(n-3)
# 메인 실행부는 위와 동일
풀이 3: 백트래킹
def sumNum(k, sum):
global count
if sum > n:
return
sum += k
if sum == n:
count += 1
sumNum(1, sum)
sumNum(2, sum)
sumNum(3, sum)
t = int(input())
for i in range(t):
n = int(input())
count = 0
sumNum(0, 0)
print(count)
주의
2 는 1+1, 2 두 가지 방법으로 볼 수 있다.
처음엔 잘못 생각해서 아래와 같이 해도 되는 거 아닌가 생각했었다 ^_^ (게다가 삼중반복문 ..)
DP 문제는 점화식만 잘 찾으면 구현은 어렵지 않으니 점화식을 잘 생각해보도록 하자 !
for i in one:
for j in two:
for k in three:
num.append(i+j+k)
for i in range(n):
x = int(input())
print(num.count(x))
728x90
