poorman

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

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

해결 방안

1. 봉지의 수를 최소화 하기 위해서는 최대한 5킬로그램 봉지를 많이 사용하면 된다.

2. N을 5로 나눈 최대치에서 1씩 줄여가면서 남은 N값이 3으로 나누어 떨어지는 순간에 봉지 개수를 리턴한다.

3. 5와 3으로 나누어 떨어지지 않는 경우에 -1을 리턴한다.

소스 코드

N = int(input())

def count_bag(x):
    bag1 = 5
    bag2 = 3
    max_bag1 = x//5
    for i in range(max_bag1+1):
        cnt1 = max_bag1 - i
        rest_x = x-(cnt1*bag1)
        if rest_x % bag2 != 0:
            continue
        cnt2 = rest_x // bag2
        return cnt1 + cnt2
    return -1

print(count_bag(N))

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

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

해결 방안 - 1

1. 재귀 함수를 이용한다. f(n+2) = f(n+1) + f(n)

2-1. 함수 f(n)는 n이 0일때 0, 1일때 1을 리턴한다.

2-2. n이 2이상의 경우에 f(n-2) + f(n-1)을 리턴한다.

소스코드 - 1

n = int(input())

def fibonacci(x):
    if x == 0:    return 0
    if x == 1:    return 1
    return fibonacci(x-1) + fibonacci(x-2)
    
print("%d" % fibonacci(n))

*재귀 함수를 사용하는 경우에 x가 커질수록 메모리 사용량과 연산 시간이 증가하여 시간 초과로 실패한다.

해결 방안 - 2

1. Dynamic Programming 알고리즘으로 n-1, n-2번째의 수만 메모리에 갱신하여 연산해 나간다.

2. 파이썬의 특징을 활용하여 x, y = y, x+y 연산으로 x에는 n-1번째 값을, y에는 n-1번째와 n-2번째의 합을 취한다.

소스코드 - 2

n = int(input())

def fibonacci(k):
    x, y = 0, 1
    for i in range(k):
        x, y = y, x+y
    return x 

print("%d" % fibonacci(n))

[Time Complexity] Python - Find Value in List vs Set vs Dict

[시간 복잡도] 파이썬 - List vs Set vs Dict 에서 Value 찾기

결론

1. Set, Dict 에서 value를 찾을 경우에 시간 복잡도 O(1)로 가장 빠름

2. 다만 List to Set/Dict conversation이 필요한 경우에 일정 값 이하의 n에서는 List를 사용