둔필승총

www.acmicpc.net/problem/14501

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

예제 입력 1

7 3 10 5 20 1 10 1 20 2 15 4 40 2 200

예제 출력 1

45

예제 입력 2

10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10

예제 출력 2

55

예제 입력 3

10 5 10 5 9 5 8 5 7 5 6 5 10 5 9 5 8 5 7 5 6

예제 출력 3

20

예제 입력 4

10 5 50 4 40 3 30 2 20 1 10 1 10 2 20 3 30 4 40 5 50

예제 출력 4

90

[문제 해설]

 N+1일째 되는 날 퇴사를 한다. 그때까지 일을 제일 많이 하면 된다. 그렇다면 다이나믹 프로그래밍을 적용했을때, 마지막에 일하는 것이 어떤 것이냐에 따라 최대값이 어떤지 비교해주면 된다.

 각 날짜에 최대를 d라는 배열에 저장해두자. 그러면 d[i]는 어떤 값이 들어올까? 이 문제의 핵심은 뒤에서부터 다이나믹 프로그래밍을 적용해야 한다는 점이다. 조건중에 n+1에는 회사에 없기때문에 일을 할 수 없다. 그래서 먼저 i날에 일을 하는 기간인 t[i]를 더한값이 n을 넘으면 안된다. 넘는다면 그 날일을 건너뛰고 그 다음날 일을 찾는 것이다. 

 만약 i+t[i]가 n을 넘지 않을 경우에는 다음과 같이 된다. 

d[i] = max(p[i] + d[i + t[i]], d[i + 1])

뒤에서부터 반복문을 쓰면 되는 것이므로 n-1에서 n이 0이 될때까지 구하면 된다. 이를 식으로 쓰면 된다.

[정답]

n = int(input())
t = []
p = []
d = [0] * (n+1)
for i in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)
# d[i]=max(p[i]+d[i+t[i]],d[i+1]) 그 일을 하는경우,하지않고 다음날 일을 하는 경우
for i in range(n - 1, -1, -1):
    if i + t[i] >n:
        d[i] = d[i + 1]
    else:
        d[i] = max(p[i] + d[i + t[i]], d[i + 1])

print(d[0])

www.acmicpc.net/problem/9625

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

예제 입력 1

1

예제 출력 1

0 1

[문제 해설]

문제 조건에서 A는 B로 변하고 B는 BA로 변한다는 사실에 입각해서 문제를 풀면된다. 결과적으로 A와 B의 개수를 구하면 되는 것이므로 K-1번 누르는 것과 K번 누르는 것의 차이를 구하면 된다. 

a는 k-1번의 b의 개수와 같다. b는 k-1번의 a의 개수와 b의 개수의 합과 같다. 

k = int(input())

a=[0]*46
b=[0]*46

a[0]=1

for i in range(1,k+1):
    a[i]=b[i-1]
    b[i]=a[i-1]+b[i-1]

print(a[k],b[k])

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])