[백준] - 1182, 14391, 11727, 11052, 15990, 10844, 2193, 11053, 14002

부분수열의 합 (1182번)

• 사이트/난이도: 백준 / 실버2
• 코드

# 실버2 부분수열의 합
import sys
from itertools import combinations
input = sys.stdin.readline

n, s = map(int, input().split())
arr = list(map(int, input().split()))
result = 0

for k in range(1, n+1):
    for comb in list(combinations(arr, k)):
        if sum(comb) == s:
            result += 1

print(result)

• 느낀점
  • n의 범위가 20밖에 안되서 조합을 이용해서 완탐으로 간단하게 풀었다.
  • dfs로 다르게 풀어볼까 고민하다가 골라야 되는 개수도 명확히 정해져있지 않고 지저분해 질거 같아서 라이브러리를 이용할수 있는 문제는 그냥 이걸로 푸는게 좋을것 같다.

종이 조각 (14391번)

• 사이트/난이도: 백준 / 골드3
• 코드

# 골드3 종이조각
# 비트마스크 - <https://vixxcode.tistory.com/m/23> 참고
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
papers = []
for _ in range(n):
    papers.append(list(map(int, input().rstrip())))
answer = 0

# 한칸당 가로, 세로 2가지 경우의 수가 있으므로 모든 칸의 경우의 수는 2^(n*m)
for i in range(1 << n*m):
    total = 0
    # 가로합
    for row in range(n):
        rowsum = 0
        for col in range(m):
            idx = row * m + col
            if i & (1 << idx) != 0: # 0 이면 세로, 아니면 가로
                rowsum = rowsum * 10 + papers[row][col]
            else:
                total += rowsum
                rowsum = 0
        total += rowsum
    
    # 세로합
    for col in range(m):
        colsum = 0
        for row in range(n):
            idx = row * m + col
            if i & (1 << idx) == 0:
                colsum = colsum * 10 + papers[row][col]
            else:
                total += colsum
                colsum = 0
        total += colsum
    answer = max(answer, total)

print(answer)

• 느낀점
  • 아예 아이디어가 생각나지 않은 문제…
  • 다른 사람풀이를 보니 비트마스크를 통해서 가로합, 세로합을 구분하고 칸 마다의 가로, 세로 경우의 수를 모두 구했다.
  • 칸 마다 가로, 세로 2가지가 가능하므로 모든 칸에 대한 경우의 수는 $2^{n*m}$ 이다.
  • 그리고 이중배열의 인덱스를 일차원으로 만들어서 해당 경우의 수와 & 연산을 하면 해당 인덱스가 가로인지 세로인지 알 수 있다.

2xn 타일링 2 (11727번)

• 사이트/난이도: 백준 / 실버3
• 코드

# 실버3 2xn 타일링 2
import sys
input = sys.stdin.readline

n = int(input())

if n == 1:
    print(1)
elif n == 2:
    print(3)
else:
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 3
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2] * 2
    print(dp[n] % 10007)

• 느낀점
  • dp 문제
  • 점화식은 dp[i] = dp[i-1] + dp[i-2] * 2 과 같은데 n길이의 직사각형을 n-1과 n-2까지 생각해 볼때 n-1에서 나머지 1을 채우는 경우는 2x1 타일로 채우는 한개이고, n-2일때는 2x1 2개와 2x2 1개로 채우는 두 개이므로 다음과 같은 점화식이 나온다.

카드 구매하기 (11052번)

• 사이트/난이도: 백준 / 실버 1
• 코드

# 실버1 카드 구매하기
import sys
input = sys.stdin.readline

n = int(input())
cards = [0] + list(map(int, input().split()))
dp = [0] * (n+1)

for i in range(1, n+1):
    dp[i] = cards[i]
    for k in range(1, i):
        dp[i] = max(dp[i], cards[k] + dp[i-k])
print(dp[n])

• 느낀점
  • dp 문제
  • 카드의 인덱스가 0부터 시작하고 dp는 1부터 시작하게 설정해서 점화식 만드는게 조금 어려웠다.
  • 그래서 cards에 [0]을 더해서 인덱스 시작위치를 맞췄다.
  • 점화식은 i개의 카드를 뽑는 최대비용 = k개의 카드 비용 + i-k개의 카드를 뽑는 최대비용 이다.
  • n의 범위가 1000이기 때문에 이중포문해도 시간초과 안난다.

1,2,3 더하기 5 (15990번)

• 사이트/난이도: 백준 / 실버2
• 코드

# 실버2 1,2,3 더하기 5
import sys
input = sys.stdin.readline

t = int(input())
dp = [[0, 0, 0] for _ in range(100001)]
# 1, 2, 3 으로 끝날 떄의 경우의 수
dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]

for i in range(4, 100001):
    # i가 1로 끝날떄의 경우의 수 = i-1이 2 or 3 으로 끝날때의 수
    dp[i][0] = (dp[i-1][1] + dp[i-1][2]) % 1000000009
    # i가 2로 끝날떄의 경우의 수 = i-2이 1 or 3 으로 끝날때의 수
    dp[i][1] = (dp[i-2][0] + dp[i-2][2]) % 1000000009
    # i가 3로 끝날떄의 경우의 수 = i-3이 1 or 2 으로 끝날때의 수
    dp[i][2] = (dp[i-3][0] + dp[i-3][1]) % 1000000009

for _ in range(t):
    n = int(input())
    print(sum(dp[n]) % 1000000009)

• 느낀점
  • 전에 푼 1,2,3 더하기와 비슷한 문제인 줄 알았는데 아무리 점화식을 세우려 해도 안됬다…
  • 다른 사람 풀이를 참고하니 이차원 배열로 생각해서 각 경우의 수를 1,2,3 으로 끝나는 수로 나누어 준후 더하는 식으로 했다.
  • 점화식은 다음과 같은데 i가 1로 끝날떄의 경우의 수 = i-1이 2 or 3 으로 끝날때의 수 로서
  • dp[i][0] = dp[i-1][1] + dp[i-1][2] 을 1뿐만 아니라 2와 3에도 적용시키면 된다.
  https://kwangkyun-world.tistory.com/m/entry/Python파이썬-15990-백준-1-2-3-더하기-5

쉬운 계단 수 (10844번)

• 사이트/난이도: 백준 / 실버1
• 코드

# 실버1 쉬운 계단 수
import sys
input = sys.stdin.readline

n = int(input())
dp = [[0] * 10 for _ in range(n+1)]
for i in range(1, 10):
    dp[1][i] = 1    

for i in range(2, n+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][j+1]
        elif j == 9:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])

print(sum(dp[n]) % 1000000000)

• 느낀점
  • 점화식 세우기 힘들었다…
  • 자리수가 k 일때 0~9까지 끝나는 수를 표로 만들어보면 바로 앞자리수에서 +1이나 -1한 경우의 수의 합이 답이 되는 것을 알 수 있다.
  • 아래 블로그에 자리수 1~3까지의 예시가 설명되어 있다.
  https://pacific-ocean.tistory.com/151

이친수 (2193번)

• 사이트/난이도: 백준 / 실버3
• 코드

# 실버3 이친수
import sys
input = sys.stdin.readline

n = int(input())

if n == 1 or n == 2:
    print(1)
else:
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 1
    for i in range(3, n+1):
        for j in range(2, i):
            dp[i] += dp[i-j]
        dp[i] += 1
    print(dp[n])

• 느낀점
  • 규칙을 찾기 쉬웠던 dp문제
  • i자리의 이진수가 주어졌을때 i-1자리는 무조건 0이어야 되므로 i-2 부터 i-3 … 1 까지 가능한 합을 구한 후 모두 0일때도 있으므로 +1 해준다.

가장 긴 증가하는 부분 수열 (11053번)

• 사이트/난이도: 백준 / 실버2
• 코드

# 실버2 가장 긴 증가하는 부분 수열
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
dp = [1] * 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))

• 느낀점
  • Dp의 대표적인 가장 긴 증가하는 부분수열 문제로 알고리즘은 다음과 같다
  • 0≤j<i 에 대해서, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

가장 긴 증가하는 부분 수열 4 (14002번)

• 사이트/난이도: 백준 / 골드4
• 코드

# 골드4 가장 긴 증가하는 부분 수열 4
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
dp = [1] * 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))

order = max(dp)
result = []
for i in range(n-1, -1, -1):
    if order == dp[i]:
        order -= 1
        result.append(a[i])
result.reverse()
print(*result)

• 느낀점
  • 가장긴 증가하는 부분수열 문제랑 완전 똑같지만 그 부분수열 개수 뿐만 아니라 해당 수열 리스트를 반환해야한다.
  • 그냥 간단하게 생각해서 dp에 이미 해당 부분수열의 순서가 들어있으므로 뒤부터 탐색하면서 해당 order랑 같은것을 넣어줬다.