Algorithms, Data Analytics

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

n, k = map(int, input().split())

array = [[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):
            array[i][j] = array[i - 1][j]
            
        else:
            array[i][j] = max(array[i - 1][j], array[i - 1][j - weight] + value)
            
print(array[n][k])

이건 좀 어려웠다.

설명 듣고 표를 그려보니까 조금 이해할 것 같다.

머리로는 이해하는데 컴퓨터로 표현하려니까 힘드네

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

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

print(dp[n])

동적프로그래밍인데, 점화식을 세우는 것이 중요하다고 한다.

문제를 어느정도 풀고 점화식을 세워본 결과 피보나치 수열과 같다고 하여 비슷하게 코딩을 해보았다.

문제

N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현재 나무에 앉아있는 새의 수가 지금 불러야 하는 수 보다 작을 때는, 1부터 게임을 다시 시작한다.

나무에 앉아 있는 새의 수 N이 주어질 때, 하나의 수를 노래하는데 1이 걸린다고 하면, 모든 새가 날아가기까지 총 몇 초가 걸리는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 새의 수 N이 주어진다. 이 값은 10^9보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

해설을 보기 전에 먼저 풀어봤다.

bird = int(input())
i = 1
time = 0

while bird > 0:
        
    bird -= i
    i += 1
    time += 1
    
    if i > bird:
        i = 1
        
print(time)
    

비슷한데

if의 위치가 while 바로 아래 있었다.

이건 어디 오든 상관 없어 보이긴 하는데 위에 있는게 더 보기 좋은 것 같기도 하고..