이번 과제는 DP 문제와 완전탐색 파트로 나누어 출제하였습니다.
- 꼭 list comprehension 을 활용하는 연습을 합시다.
A. 일곱 난쟁이
해설 및 포인트
블랙잭 문제와 유사하게 반복문으로 해결하면 됩니다. 단, 9명 중 7명을 선택하는 것이 아닌 2명을 선택하는 것입니다.
이렇게 N개 중 M개를 선택하는 문제는 N-M으로 치환할 수 있다는 점을 기억합시다.
source code
A = [int(input()) for i in range(9)]
for i in A:
for j in A:
if i!=j and i+j == sum(A)-100:
A.remove(i)
A.remove(j)
for i in sorted(A) : print(i)
B. 찍기
해설 및 포인트
패턴을 어떻게 반복문으로 표현할 수 있을까를 묻는 문제입니다. 여러가지 방법이 있겠지만, 2가지 방법을 소개합니다.
- modulo 연산 (%)을 사용한 반복
- 정답패턴을 매우 길게 만들어 단순한 비교
각각의 방법에는 장단점이 있습니다.
1의 방법은 비교적 % 연산을 사용하여야한다는 번거러움이 있지만, 메모리를 효율적으로 사용할 수 있고, 2의 방법은 zip을 이용하여 간단하게 할 수 있다는 장점이 있습니다.
zip, enumerate 등을 활용하는 연습도 틈틈히 합시다 :)
source code
pat = ['ABC', 'BABC', 'CCAABB']
name = ['Adrian', 'Bruno', 'Goran']
N, ans = int(input()), input()
# 1번 방법 : modulo
# def f(N, str, ans):
# l = len(str)
# return sum([int(str[i%l]==ans[i]) for i in range(N)])
# 2번 방법 : 패턴을 길게
def f(N, str, ans):
return sum([int(a==b) for a, b in zip(str, ans)])
score = [f(N, i*50, ans) for i in pat]
mx = max(score)
print(mx)
for sc, n in zip(score, name):
if sc == mx : print(n)
C. 체스판 다시 칠하기
해설 및 포인트
이 문제는 전체적인 과정을 쪼개서 생각하는 것이 포인트입니다.
- 8 x 8 체스판을 흑백으로 칠했을 때, 수정해야하는 개수
- 흑백으로 시작하는 패턴
- 백흑으로 시작하는 패턴
- N x M에서 8 x 8을 선택할 수 있는 방법
- (N-8+1)*(M-8+1)가지
- 선택 방법
- index로 처리 (이 방법이 간단)
- 부분배열로 처리 (slicing 복잡)
또한 흑과 백의 공간은 행번호 + 열번호의 홀짝성을 사용하면 됩니다. 같은 색 공간은 행번호 + 열번호가 모두 홀 또는 모두 짝입니다.
source code
저는 케이스를 4가지로 나눴습니다.
- W칸에 W인 경우
- W칸에 B인 경우
- B칸에 W인 경우
- B칸에 B인 경우
이 중에 실제 색칠을 다시 해야하는 칸 수는 (W, B)와 (B, W) 경우입니다. 이렇게 조건이 서로 다를 때 참을 반환하는 함수는 xor 연산을 사용하면 좀 더 짧게 표현할 수 있습니다.
xor 연산은 다음과 같습니다.
- 1 xor 1 = 0
- 1 xor 0 = 1
- 0 xor 1 = 1
- 0 xor 0 = 0
N, M = map(int, input().split())
A = [input() for _ in range(N)]
ans = 64
def ck(i, j):
w, b = 0, 0 # 시작점이 W일때와 시작점이 B일때
for x in range(8):
for y in range(8):
# 보고 있는 위치가 W여야하지만 B일 때, B여야하지만 W일때를
# 더해주기 위한 xor연산
w += (A[i+x][j+y] == 'W') ^ (x+y)%2
# 위 케이스와 반대
b += (A[i+x][j+y] == 'B') ^ (x+y)%2
return min(w, b)
for i in range(N-8+1):
for j in range(M-8+1):
# 8 by 8을 자를때 시작 인덱스를 넘겨줌
ans = min(ck(i, j), ans)
print(ans)
D. 1로 만들기
해설 및 포인트
이 문제는 2가지 풀이 방법이 있습니다.
- BFS로 해결하는 방법
- DP로 해결하는 방법
각 방법을 설명하면 다음과 같습니다.
BFS는 숨바꼭질 문제와 유사합니다. 초기 X에서 갈 수 있는 방향은 총 3가지 입니다. (X//3, X//2, X-1) 이제 이를 BFS로 하여 가장 먼저 1이 되는 답이 정답입니다.
DP는 반대로 1부터 시작하는 Bottom-UP DP로 해결할 수 있습니다.
DP[i]는 i가 1이 되기 위한 횟수를 저장한다고 하면, DP[2*i], DP[3*i], DP[i+1]은 만약 비어있다면 DP[i]+1, 이미 채워져있다면 min(DP[i]+1, DP[x])와 같이 채우면 됩니다.
source code
# BFS로 해결
from collections import deque
N = int(input())
ck = [-1 for _ in range(N+1)]
q = deque()
q.append(N)
ck[N] = 0
while len(q):
front = q.popleft()
if front == 1 :
print(ck[front])
break
if front % 3 == 0 and ck[front//3] == -1:
q.append(front//3)
ck[front//3] = ck[front] + 1
if front % 2 == 0 and ck[front//2] == -1:
q.append(front//2)
ck[front//2] = ck[front] + 1
if ck[front-1] == -1:
q.append(front-1)
ck[front-1] = ck[front] + 1
DP도 2가지 방법으로 할 수 있습니다.
DP[i]를 만들기 위해서 i보다 작은 수에서 가져오는 것DP[i]에서 i보다 큰 값을 채우는 방법
저는 이 문제에서는 2번째 방법이 더 직관적이라 생각하여, 그렇게 풀었습니다.
# DP로 해결
N = int(input())
DP = [N+1 for _ in range(N+1)]
DP[1] = 0
for i in range(1, N):
for x in [i*3, i*2, i+1]:
if x <= N : DP[x] = min(DP[i]+1, DP[x])
print(DP[N])
E. 1, 2, 3 더하기
해설 및 포인트
계단오르기 문제와 거의 동일합니다.
N까지 도달하기 위해서는 마지막에 1, 또는 2, 또는 3으로 도착해야합니다.
이는 간단하게 DP 식으로 쓰면 DP[i] = DP[i-1] + DP[i-2] + DP[i-3]
즉, N-1까지 만든 조합에 1을 붙이고, N-2까지 만든 조합에 2를 붙이고, N-3까지 만든 조합에 3을 붙이는 방법입니다.
source code
DP = [0 for _ in range(13)]
DP[0] = 1
for i in range(1, 13):
for x in range(1, 4):
if i >= x : DP[i] += DP[i-x]
for _ in range(int(input())):
print(DP[int(input())])
F. 가장 긴 감소하는 부분 수열
해설 및 포인트
가장 긴 증가하는 부분 수열의 부등호만 바꾸면 되는 문제입니다.
source code
N, A = int(input()), list(map(int, input().split()))
DP = [1 for _ in range(N)]
for i in range(1, N):
for j in range(i):
if A[j] > A[i]:
DP[i] = max(DP[i], DP[j]+1)
print(max(DP))