IT-garden

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

t=int(input())

while t:
    z=[1,0]
    o=[0,1]
    n=int(input())
    
    for i in range(2,n+1):
        z.append(z[i-1] + z[i-2])
        o.append(o[i-1] + o[i-2])

        
    print(z[n],o[n])
    t -= 1

fibonacci(0) = 1, 0
fibonacci(0) = 0, 1
fibonacci(2) = fibonacci(1) + fibonacci(0)
1, 1 = 1, 0 + 0, 1
fibonacci(3) = fibonacci(2) + fibonacci(1)
1, 2= 1, 1 + 0, 1

규칙은 피보나치 수열처럼 앞 2개의 0이 출력되는 횟수와 1이 출력되는 횟수를 합하면 됩니다.

백준 알고리즘 1003번 : www.acmicpc.net/problem/1003

문제

피보나치 수는 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은 45보다 작거나 같은 자연수이다.

출력

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

예제 입력과 출력

정답

m=[0]*46
def _2747(n):
    if n <= 1:
        m[n] = n
        return n
    else:
        if m[n] > 1:
            return m[n]
        m[n] = _2747(n-1) + _2747(n-2)
        return m[n]

print(_2747(int(input())))

재귀호출을 이용해 계산하는데 한번 구한 답은 배열에 저장해야 시간초과가 나지 않습니다.
n이 1이하인 경우는 n을 리턴해주고 n이 1이상인 경우는 m[n] = _2747(n-1) + _2747(n-2)을 통해 m[n]을 구합니다.
큰 문제에서 작은 문제를 구하는 구조인데 작은 문제의 답이 있는 경우는 m 배열에 있는 m[n]을 활용해 계산 횟수를 줄여줍니다.

n=int(input())

dp=[0]*46
dp[1]=1

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

print(dp[n])

백준 알고리즘 2747번 : www.acmicpc.net/problem/2747

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

n = int(input())
a = [0]*(n+1)

for i in range(2, n+1):
    a[i] = a[i-1] + 1
    if i % 3 == 0 and a[i//3] + 1 < a[i]:
        a[i] = a[i//3] + 1
    if i % 2 == 0 and a[i//2] + 1 < a[i]:
        a[i] = a[i//2] + 1
        
print(a[n])

1에서 n까지의 횟수를 더해가는 방식입니다.

백준 알고리즘 1463번 : www.acmicpc.net/problem/1463

문제

지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다.

예제 입력과 출력

알고리즘 분류

수학
브루트 포스
재귀 호출
탐색

정답

import sys

n=int(sys.stdin.readline().strip())
a=[0]*10
b=1
while n != 0:
    while n % 10 != 9:
        for i in str(n):
            a[int(i)] += b
        n -= 1
        
    if n < 10:
        for k in range(n+1):
            a[k] += b
        a[0] -= b
        break
    
    else:
        for i in range(10):
            a[i] += (n//10 + 1) * b
    a[0] -= b
    b *= 10
    n //= 10
    
for i in a:
    print(i,end=' ')

백준 알고리즘 1019번 : www.acmicpc.net/problem/1019

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

예제 입력과 출력

알고리즘 분류

이분 탐색

정답

n,c=map(int,input().split())
a=list(int(input()) for i in range(n))

a.sort()

low = 1
high = a[-1]-a[0]

while high >= low:
    m = (low+high) // 2

    r = 1 
    home = a[0] #첫번째에는 공유기 세우기

    for i in range(1,n):
        if home + m <= a[i]: 
            r += 1
            home = a[i] # 공유기가 최근에 설치된 집
            
    if r < c:
        high = m -1
    elif r >= c:
        b = m
        low = m + 1

print(b)

high는 첫번째 집과 마지막 집의 차이입니다.

백준 알고리즘 2110번 : www.acmicpc.net/problem/2110

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. 

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다. 

예제 입력과 출력

알고리즘 분류

이분 탐색

정답

n=int(input())
a=list(map(int,input().split()))
m=int(input()) # 총 예산

a.sort()

low = 1
high = max(a)
r = 0
while high >= low:
    mid = (low+high) //2 # 상한액
    c = sum([mid if i > mid else i for i in a])

    if m >= c:
        low = mid + 1
        r = mid
    else:
        high = mid - 1

print(r)

백준 알고리즘 2512번 : www.acmicpc.net/problem/2512