1904 01타일, 12865 평범한 배낭, 11053 가장 긴 증가하는 부분 수열

 

1904 01타일, 12865 평범한 배낭, 11053 가장 긴 증가하는 부분 수열

 

1904 01타일

# 첫번째 풀이(시간 초과)
n = int(input())

a = 1
b = 2
temp = 0
for _ in range(2, n):
	temp = a + b
	a = b
	b = temp		
if n == 1:
	print(1)	
else:
	print(b % 15746)
    
# 두번째 풀이
n = int(input())

array = [0] * 1000001
array[1] = 1
array[2] = 2

for i in range(3, n+1):
	array[i] = (array[i-1] + array[i-2]) % 15746
	
print(array[n])

- 왜 배열을 쓸 떼 없이 많이 만든 게 시간 초과가 안 뜰까

- 왜 변수만 사용한게 문제일까 if문이 메모리나 시간을 많이 쓰는 것 같음

 

 

12865 평범한 배낭

n, k = map(int, input().split())
dp = [[0] * (k+1) for _ in range(n+1)]

for i in range(1, n+1):
	weight, value = map(int, input().split())
	for j in range(1, k+1):
		if j < weight:
			dp[i][j] = dp[i-1][j]
		else:
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value)
			
print(dp[n][k])

- 돌아가는 과정은 이해가지만 점화식 세우는 과정을 모르겠음.

- 동적 프로그래밍 연습 필요

 

 

11053 가장 긴 증가하는 부분 수열

n = int(input())
array = list(map(int, input().split()))
count = [1] * n 

for i in range(1, n):
	for j in range(0, i):
		if array[j] < array[i]:
			count[i] = max(count[i], count[j]+1)
			
print(max(count))

- 문제 잘 읽어보기(등차 수열이랑 헷갈림)

- 리스트 만들 때 기본 리스트랑 이중 리스트 코드 확인

# 기본 리스트
count = [1] * 10
print(count)

# 이중 리스트
count2 = [[1] for _ in range(10)]
print(count2)