20200320 알고리즘
1. 휴가
카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동 안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들어 휴가를 떠나려 한다. 현수가 다니는 회사에 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다. 각각의 상담은 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P로 이 루어져 있다.
만약 N = 7이고, 아래와 같이 예약이 잡혔있다면
1일에 잡혀있는 상담은 총 4일이 걸리며, 상담했을 때 받을 수 있는 금액은 20이다. 만약 1일 에 예약된 상담을 하면 4일까지는 상담을 할 수가 없다. 하나의 상담이 하루를 넘어가는 경우가 많기 때문에 현수는 예약된 모든 상담을 혼자 할 수 없어 최대 이익이 나는 상담 스케쥴을 짜기로 했다.
휴가를 떠나기 전에 할 수 있는 상담의 최대 이익은 1일, 5일, 7일에 있는 상담을 하는 것이 며, 이때의 이익은 20+30+10=60이다. 현수가 휴가를 가기 위해 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
▣ 입력설명 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다. 둘째 줄부터 1일부터 N일까지 순서대로 주어진다. (1 ≤ T ≤ 7, 1 ≤ P ≤ 100)
▣ 출력설명 첫째 줄에 현수가 얻을 수 있는 최대 이익을 출력한다.
▣ 입력예제 1
7
4 20
2 10
3 15
3 20
2 30
2 20
1 10▣ 출력예제 1
60
Solution
import sys
sys.stdin = open("input60.txt", "rt")
def DFS(L, money_sum):
global max
if L == n+1:
if max < money_sum:
max = money_sum
else:
if L + times[L] <= n+1:
DFS(L + times[L], money_sum + money[L])
DFS(L+1, money_sum)
if __name__ == '__main__':
n = int(input())
times = [0]
money = [0]
for _ in range(n):
t, m = map(int, input().split())
times.append(t)
money.append(m)
max = - 2147000000
DFS(1, 0)
print(max)2. 양팔저울
무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0 으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고, 각 추의 무게가 {1, 2, 6}이 면, S=9이고, 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과 같이 그릇에 담을 수 있다. X는 그릇에 담는 물의 무게이고, ⎕은 그릇을 나타낸다.
만약 추의 무게가 {1, 5, 7}이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담을 수 없다. K(3<=K<=13)개의 추 무게가 주어지면, 1부터 S사이의 정수 중 측정이 불가능한 물의 무게는 몇 가지가 있는 지 출력하는 프로그램을 작성하세요.
▣ 입력설명 첫 번째 줄에 자연수 K(3<=K<=13)이 주어집니다. 두 번째 줄에 K개의 각 추의 무게가 공백을 사이에 두고 주어집니다. 각 추의 무게는 1부터 200,000까지이다.
▣ 출력설명 첫 번째 측정이 불가능한 가지수를 출력하세요.
▣ 입력예제 1
3
1 5 7▣ 출력예제 1
2
Solution
import sys
sys.stdin = open("input61.txt", "rt")
def DFS(L, sum):
if L == n:
if 0 < sum <= tot:
res.add(sum)
else:
DFS(L+1, sum + a[L])
DFS(L+1, sum - a[L])
DFS(L+1, sum)
if __name__ == '__main__':
n = int(input())
a = list(map(int, input().split()))
tot = sum(a)
res = set()
DFS(0, 0)
print(tot - len(res))3. 동전 바꿔주기
명보네 동네 가게의 현금 출납기에는 k가지 동전이 각각n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다.예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은4가지 방법으로 교환할 수 있다. 20 = 10×2 20 = 10×1+5×2 20 = 10×1+5×1+1×5 20 = 5×3+1×5 입력으로 지폐의 금액 T, 동전의 가지수 k, 각 동전 하나의금액 pi와 개수 ni가 주어질 때 (i=1,2,…,k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는프로그램을 작성하시오. 방법의 수는 231 을 초과하지않는 것으로 가정한다.
▣ 입력설명 첫째 줄에는지폐의 금액 T(0<T≤10,000), 둘째 줄에는 동전의 가지 수k(0<k≤10), 셋째 줄부터 마지막 줄까지는 각 줄에 동전의금액 pi(0<pi≤T)와 개수 ni(0<ni≤10)가 주어진다. pi와 ni 사이 에는 빈 칸이 하나씩 있다.
▣ 출력설명 첫 번째 줄에 동전 교환 방법의 가지 수를 출력한다.(교환할 수 없는 경우는 존재하지 않는 다.)
▣ 입력예제 1
20
3
5 3
10 2
1 5▣ 출력예제 1
4
Solution
import sys
sys.stdin = open("input62.txt", "rt")
def DFS(L, sum):
global cnt
if sum > target:
return
if L == n:
if sum == target:
cnt += 1
else:
for i in range(amount[L]+1):
DFS(L+1, sum + c[L] * i)
if __name__ == '__main__':
target = int(input())
n = int(input())
c = list()
amount = list()
for _ in range(n):
p, q = map(int, input().split())
c.append(p)
amount.append(q)
cnt = 0
DFS(0, 0)
print(cnt)4. 동전 분배하기
N개의 동전을 A, B, C 세명에게 나누어 주려고 합니다. 세 명에게 동전을 적절히 나누어 주어, 세 명이 받은 각각의 총액을 계산해, 총액이 가장 큰 사람과 가장 작은 사람의 차가 최소가 되도록 해보세요. 단 세 사람의 총액은 서로 달라야 합니다.
▣ 입력설명 첫째 줄에는 동전의 개수 N(3<=N<=12)이 주어집니다. 그 다음 N줄에 걸쳐 각 동전의 금액이 주어집니다.
▣ 출력설명 총액이 가장 큰 사람과 가장 작은 사람의 최소차를 출력하세요.
▣ 입력예제
7
8
9
11
12
23
15
17▣ 출력예제 5
Solution
import sys
sys.stdin = open("input63.txt", "rt")
def DFS(L):
global res
#if res < max(div) - (min(div) + sum(cv[L:])):
# return
if L == n:
if div[0] != div[1] and div[0] != div[2] and div[1] != div[2]:
tmp = max(div) - min(div)
if tmp < res:
res = tmp
else:
for i in range(3):
div[i] += cv[L]
DFS(L+1)
div[i] -= cv[L]
if __name__ == '__main__':
n = int(input())
cv = list()
div = [0, 0, 0]
res = 2147000000
for _ in range(n):
cv.append(int(input()))
DFS(0)
print(res)리스트의 원소 중복 체크 방법#2
tmp = set()
for v in div:
tmp.add(v)
if len(tmp) != 3:
return false5. 알파코드
철수와 영희는 서로의 비밀편지를 암호화해서 서로 주고받기로 했다. 그래서 서로 어떻게 암 호화를 할 것인지 의논을 하고 있다. 영희 : 우리 알파벳 A에는 1로, B에는 2로 이렇게 해서 Z에는 26을 할당하여 번호로 보내기 로 하자.
철수 : 정말 바보같은 생각이군!! 생각해 봐!! 만약 내가 “BEAN”을 너에게 보낸다면 그것을 암 호화하면 25114이잖아!! 그러면 이것을 다시 알파벳으로 복원할 때는 많은 방법이 존재하는 데 어떻게 할건데… 이것을 알파벳으로 바꾸면 BEAAD, YAAD, YAN, YKD 그리고 BEKD로 BEAN말고도 5가지나 더 있군.
당신은 위와 같은 영희의 방법으로 암호화된 코드가 주어지면 그것을 알파벳으로 복원하는데 얼마나 많은 방법인 있는지 구하세요.
▣ 입력설명 첫 번째 줄에 숫자로 암호화된 코드가 입력된다. (코드는 0으로 시작하지는 않는다, 코드의 길 이는 최대 50이다) 0이 입력되면 입력종료를 의미한다.
▣ 출력설명 입력된 코드를 알파벳으로 복원하는데 몇 가지의 방법이 있는지 각 경우를 출력한다. 그 가지 수도 출력한다. 단어의 출력은 사전순으로 출력한다.
▣ 입력예제 1
25114
▣ 출력예제 1
BEAAD
BEAN
BEKD
YAAD
YAN
YKD
6Solution1
import sys
sys.stdin = open("input64.txt", "rt")
def DFS(L, P):
global cnt
if L == size:
for i in range(P):
print(chr(res[i] + 64), end='')
print()
cnt += 1
else:
for i in range(1, 27):
if a[L] == i:
res[P] = i
DFS(L+1, P+1)
elif i >= 10 and a[L] == i//10 and a[L+1] == i % 10:
res[P] = i
DFS(L+2, P+1)
if __name__ == '__main__':
a = list(map(int, input()))
size = len(a)
res = [0] * size
a.append(-1)
cnt = 0
DFS(0, 0)
print(cnt)상태트리 구성 기준: 리스트의 각 자리 1~26 매칭 되는지 체크
Solution2
import sys
sys.stdin = open("input64.txt", "rt")
def DFS(L, sum):
global cnt
if L == size:
print(sum)
cnt += 1
else:
tmp = int(a[L: L + 1])
if tmp != 0:
DFS(L + 1, sum + chr(tmp + 65 - 1))
if L + 2 <= size:
tmp = int(a[L: L + 2])
if tmp <= 26:
DFS(L + 2, sum + chr(tmp + 65 - 1))
if __name__ == '__main__':
a = input()
size = len(a)
cnt = 0
DFS(0, '')
print(cnt)상태트리 구성 기준 : 1개로 자른다 or 2개로 자른다
![[HongDongUk]](/static/a60d793d17c3aad0361c9192a3b51381/a12fc/profile.png)