둔필승총

www.acmicpc.net/problem/1463

문제

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

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

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

[문제 해설]

 1로 만들기는 다이나믹 프로그래밍의 대표적인 예이다. 1로 만드는 3가지 방법은 3으로 나누기, 2로 나누기, 1 빼기 이다. 어떤 것이 연산을 더 적게 할 수 있는지 생각하면 된다. 

 먼저 d 배열은 만든다. d 배열은 각각의 input n에서 최소의 값을 저장한 배열이다. n은 1보다 크기 때문에 반복문은 2부터 n까지 돌린다. 먼저 d[i]는 d[i-1] +1은 1빼는 것이므로 먼저 저장해두고 비교한다. 비교할 것은 3으로 나누는 것과 2로 나누는 것을 비교해주면 된다. 

3으로 나누어 떨어진다고 하면 d[i] = d[i//3] + 1 이다. 1을 더해주는 것은 3으로 나누는 연산을 해주었기 때문이다. 그럼 1을 빼는 것이 연산을 더 줄일 수 있는지 3으로 나누는 것이 더 줄일 수 있는지 구한다. 이 식이 바로

d[i]=min(d[i//3]+1, d[i])

 이다. 2로 나누는 것도 똑같이 해주면 된다.

# 1로 만들기
import sys
input = sys.stdin.readline

n = int(input())

d = [0]*1000002

for i in range(2,n+1):
    d[i] = d[i - 1] + 1
    if i%3==0:
        d[i]=min(d[i//3]+1, d[i])
    if i%2==0:
        d[i]=min(d[i//2]+1, d[i])

print(d[n])

www.acmicpc.net/problem/2579

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력 1 복사

6 10 20 15 25 10 20

예제 출력 1 복사

75

[문제 해설]

일단.acmicpc.net/problem/2579

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.



예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.



계단 오르는 데는 다음과 같은 규칙이 있다.

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력 1 복사

6 10 20 15 25 10 20

예제 출력 1 복사

75

[문제 해설]

 일단 최대값을 구해야 된다는 사실을 알 수 있다. max()를 쓸 생각을 하고 있자.

계단을 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 그래서 생각할 수 있는게

r[i]의 경우에 r[i-2]에 마지막 계단을 밟는 경우와 r[i-1]의 경우에서 마지막 계단을 밟는 경우 2개 중 어느게 최대값인지 계산하면 된다고 생각했다.

 근데, 연속된 세 개의 계단을 모두 밟아서는 안된다는 조건이 있다. r[i-1]의 경우에서 마지막 계단을 밟는 경우가 연속된 세 개의 계단을 밟은것인지 아닌지 확신할 수 없다.

 그래서 r[i-3]까지 생각해야된다. 그래서 r[i]는 r[i-2]+d[i] (여기서 d[i]는 i번째 계단의 점수)와 r[i-3]+ d[i-1] + d[i] 중 최대값을 구하면 된다.

 그리고 초기값 n이 0일때는 0, n이 1일 때는 계단 첫번째 값 (d[0]), n이 2일 때는 d[0]+d[1]이 된다. 

n = int(input())
d = []
r = [0] * n
for _ in range(n):
    d.append(int(input()))

if n==0:
    print(0)
elif n==1:
    print(d[0])
elif n==2:
    print(d[0]+d[1])
else:
    r[0] = d[0]
    r[1] = d[0] + d[1]
    r[2] = max(d[0] + d[2], d[1] + d[2])

    for i in range(3, n):
        r[i] = max(r[i - 2] + d[i], r[i - 3] + d[i - 1] + d[i])

    print(r[n - 1])

www.acmicpc.net/problem/9095

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

[문제 풀이]

다이나믹 프로그래밍의 대표적인 문제이다. 2 x n의 타일링은 일단 가로가 관건이다. 

타일은 1x2, 2x1 밖에 없다. n길이의 가로를 채울려면 일단 n-2길이를 채우고 1x2타일을 2개 넣으면된다.

또, n-1길이를 채우고 2x1타일을 채우면 된다.

따라서 다이나믹 프로그래밍에 따라 점화식을 세워보자.

d[i]=d[i-2]+d[i-1]

그리고 초기값을 구하면 된다. d[1]일 때는 2x1밖에 안들어간다. d[1]=1

d[2]는 2x1 타일 2개 아니면 1x2 타일 2개를 쓰면 채워진다. d[2] = 2

초기값을 채우고 나서 나머지 식을 구하면 된다.

#2Xn 타일링

n = int(input())

d = [0]*1001
d[1]=1
d[2]=2
for i in range(3,n+1):
    d[i]=d[i-2]+d[i-1]

result = d[n]%10007
print(result)

불린 값으로 형 변환을 할 때는, 보통 true 값이 나오지만, 빈문자(''), 0, 그리고 NaN 값은 false로 변환이 된다.

1. Boolean("false")

2. Boolean(6 % 2)

3. Boolean(NaN) || Boolean('0')

4. Boolean(typeof false)


(1) 불린 false가 아니라 문자열 false이기 때문에 결과는 true이다.

(2) 6 % 2의 결과는 0이다.결국 Boolean(0)이 되기 때문에 결과는 false가 된다.

(3) Boolean(NaN)은 false고, Boolean('0')은 문자열 0을 불린형으로 형 변환 한 것이기 때문에 true이다. 결국 false || true 가 되기 때문에, 결과는 true가 된다.

(4) typeof 연산자를 사용하고 있는데, 이 선택지를 다시 정리하면 Boolean('boolean') 이 된다. 문자열 boolean을 불린형으로 형 변환 하기 때문에 결과는 true다.

 Brute-Force Attack은 우리말로 무차별 대입 공격이란 뜻이다. 이 말은 정말 무차별적으로 모든 방법을 시도하는 것을 뜻한다. Brute-Force 알고리즘도 비슷하다.

 예를 들어 자물쇠 0~99까지 가능하다면 0부터 99까지 모든 경우의 수를 시도하는 것이다. 힘들긴 하겠지만 시간만 있다면 가능한 것이다. 브루트 포스는 말 그대로 가장 순진한 알고리즘 접근법이다. 가능한 모든 조합을 찾아서 계산하면 되는 것이다.

 브루트 포스 알고리즘은 모든 경우의 수를 봐서 확실한 답을 구한다는 장점이 있지만 알고리즘 자체는 비효율적이다. 특히, input이 클수록 더 비효율적이라는 생각이 들것이다. 

 브루트 포스는 직관적이고 명확하고 답을 확실하게 찾을 수 있다는 장점이 있다. 그래서 효율적인 알고리즘의 첫 시작은 브루트 포스이기때문에 알고리즘을 배울 필요가 있는 것이다.

아래에 있는 브루트 포스 알고리즘의 예시를 보자.

[문제 설명]

카드 두 뭉치가 있습니다.

왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 두 수의 곱이 가장 크게 만들고 싶은데요. 어떻게 하면 가장 큰 곱을 구할 수 있을까요?

함수 max_product는 리스트 left_cards와 리스트 right_cards를 파라미터로 받습니다.

left_cards는 왼쪽 카드 뭉치의 숫자들, right_cards는 오른쪽 카드 뭉치 숫자들이 담겨 있고, max_product는 left_cards에서 카드 하나와 right_cards에서 카드 하나를 뽑아서 곱했을 때 그 값이 최대가 되는 값을 리턴합니다.

def max_product(left_cards, right_cards):
	print(max_product([1, 6, 5], [4, 2, 3]))
	print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
	print(max_product([-1, -7, 3], [-4, 3, 6])) 

[풀이과정]

 브루트 포스 방법으로 for문을 2개 사용하여 풀면 된다. 처음에 max를 사용하여 left_cards 와 right_cards에서 하나씩 최대값을 뽑아서 곱했는데 그러면 음수와 음수의 곱이 최대가 될 경우를 생각못할 수 있다. 

그래서 일일이 다 구해서 최대값을 구하면 된다.

[해답]

def max_product(left_cards, right_cards):
    bigg=0
    for left_card in left_cards:
        for right_card in right_cards:
            wow = left_card*right_card
            if wow>bigg:
                bigg=wow
    return bigg
# 테스트
print(max_product([1, 6, 5], [4, 2, 3]))
print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
print(max_product([-1, -7, 3], [-4, 3, 6]))

#Tip#

3중 반복문에서 3번째 반복문을 실행 후 2번째 반복문을 다시 실행하는 과정을 재귀로 구현한 코드에서 현재 실행 중인 함수를 호출한 곳으로 돌아가는 과정으로 비유하면 백트래킹 기법을 적용했다고 한다. 백트래킹을 브루트 포스를 수행하는 방법 중 하나로 본다.

www.acmicpc.net/problem/2839

문제

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

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

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

입력

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

출력

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

[풀이]

 일단 d배열의 전체를 10001로 저장해두고 d[0]=0을 해둔다. 보텀업으로 아래부터 하나하나씩 채워가기 위해서 둔것이다. 예를 들어 n을 18을 입력하였다면 18에서 5를 뺀 값은 13이다. 그럼 d[13]이 저장되어있다면 d[18]과 d[13]+1 중에서 최소값이 어떤 것인지 찾아내면 되는 것이다. 5를 뺀 d[13]이 10001이면(그러니까 5kg 3kg 두 개로 배달이 불가능한 경우일때)는 d[18]에서 3을 뺀 d[15]가 있는지 한번 살펴보는 것이다. 그럼 또 d[15]+1과 d[18]의 최소값을 찾으면 되는것이다. 예전에 '효율적인 화폐 구성' 문제에서 아이디어를 받았다. (N가지 종류의 화폐로 비용을 지불하는 문제)

n = int(input())

d = [10001]*5001
d[0]=0
for i in range(3,n+1):
    if i-5>=0 and d[i-5]!=10001:
        d[i]=min(d[i],d[i-5]+1)
    if d[i-3]!=10001:
        d[i]=min(d[i],d[i-3]+1)

if d[n]==10001:
    print(-1)
else:
    print(d[n])

www.acmicpc.net/problem/9095

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1

3 4 7 10

예제 출력 1

7 44 274

[풀이]

 먼저, 숫자가 3개 1,2,3이 있다는 사실을 안다. 4부터는 4하나로는 만들 수가 없다. 배열 d에 d[1], d[2], d[3]에 대한 값을 저장해두고 d[1], d[2], d[3]을 이용해서 나머지 4부터 10까지의 배열값을 저장할려고 했다.

4는 1에 3을 더한것, 2에 2를 더한것, 3에 1을 더한것이므로 d[4] = d[1] + d[2] + d[3] 이라고 생각할 수 있다.

5는 1에 4를 더한것, 2에 3을 더한것, 3에 2를 더한것, 4에 1을 더한것이라고 생각하면 되는데 1,2,3밖에 없으므로

d[5] = d[4] + d[3] + d[2] 까지만 하면 된다.

d[i] = d[i-1] + d[i-2] + d[i-3]이라는 점화식을 끌어오면 된다.

#1,2,3 더하기

T = int(input())
d=[0]*11
d[1]=1
d[2]=2
d[3]=4

for i in range(4,11):
    d[i]=d[i-3]+d[i-2]+d[i-1]
for i in range(T):
    n = int(input())
    print(d[n])

 컴퓨터를 이용하여 최적의 해를 구하는데 메모리 공간에는 한계가 있다. 그래서 우리는 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

 반대로, 다이나믹 프로그래밍은 메모리 공간을 약간 더 사용하여 연산 속도를 증가시키는 방법이다. 다이나믹 프로그래밍은 탑다운과 보텀업 두가지 방식으로 나뉘다. 그리고 메모이제이션 기법까지 알아야 된다.

 피보나치 수열은 다이나믹 프로그래밍의 대표적인 예이다. 점화식으로 표현하여 푸는 것을 다이나믹 프로그래밍의 문제라고 생각하면 된다. 

def fibo(x):
	if x==1 or x==2 :
    	return 1
    return fibo(x-1)+fibo(x-2)

다음과 같이 코드를 짜면 fibo(x)에서 x에 값이 중복되면 계속 새로 계산해야된다는 단점이 있다. 그렇다면 시간복잡도가 기하급수적으로 늘어난다. 따라서 다이나믹 프로그래밍을 통해 문제를 해결한다. 다이나믹 프로그래밍을 항상 사용할 수 수는 없고 다음 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 다음과 같은 조건을 만족한다. 이 문제를 메모이제이션(Memoization)기법을 사용해서 해결할 수 있다.

아래는 탑다운 방식이다.

#한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화

d = [0]*100

def fibo(x):
    if x==1 or x==2:
        retun 1
    if d[x]!=0:
        return d[x]
    d[x]=fibo(x-1)+fibo(x-2)
    return d[x]

이렇게 되면 시간복잡도가 O(N)이 된다.

 이처럼 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위하여 작은 문제를 호출한다고 하여 탑다운 방식이라고 말한다. 

 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 한다. 피보나치 수열 문제를 보텀업으로도 풀어보자.

d = [0]*100
d[1]=1
d[2]=1
n=99

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

시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있으므로 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다.