say repository

코드

import sys
n,k = map(int,sys.stdin.readline().split())
d = [0]*(k+1)
coins = []
for i in range(n):
    coins.append(int(sys.stdin.readline()))
d[0] = 1
for i in coins:
    for j in range(i,k+1): #동전부터 순회
        if j-i >= 0:
            d[j] += d[j-i]
print(d[k])

풀이

d[i] 는 i원을 만들기 위한 경우의 수라고 생각하면 된다.

동전의 종류만큼 포문을 돌면서 d[j] += d[j-i] 를 해주면 된다.

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

코드

import sys
from collections import deque
m, n, k = map(int,sys.stdin.readline().split())
arr = [[0]*n for _ in range(m)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

#직사각형 k개 1로 표시
for i in range(k):
    x1, y1, x2, y2 = map(int,sys.stdin.readline().split())
    for y in range(y1,y2):
        for x in range(x1,x2):
            arr[y][x] = 1
# print(arr)

#bfs
result = []

for i in range(m):
    for j in range(n):
        if arr[i][j] == 0: #갈 수 있는 길이면
            cnt = 1
            arr[i][j] = 1
            #bfs
            q = deque()
            q.append((i,j))
            while q:
                y,x = q.popleft()
                for c in range(4):
                    ny = y+ dy[c]
                    nx = x+ dx[c]
                    if 0<=ny<m and 0<=nx<n and arr[ny][nx] == 0:
                        cnt += 1
                        arr[ny][nx] = 1
                        q.append((ny,nx))
            result.append(cnt)
print(len(result))
result.sort()
for i in result:
    print(i,end=" ")

풀이

bfs로 풀이했다.

x,y가 y,x로 위치가 바뀌어서 계속 헷갈렸다.

import sys
from collections import deque
n, m = map(int,sys.stdin.readline().split())
arr = []
for i in range(n):
    arr.append(list(map(int,sys.stdin.readline().rstrip())))
#bfs
dx = [-1,0,1,0]
dy = [0,1,0,-1]
q = deque()
q.append((0,0))
while q:
    x,y = q.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<m and arr[nx][ny] == 1:
            arr[nx][ny] = arr[x][y] + 1
            q.append((nx,ny))
print(arr[n-1][m-1])

풀이

bfs로 풀었다.

(0,0) 부터 이동해서 arr값이 1이면 이동하고 +1 해준다.

마지막 도착지점을 출력해주면 된다.

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

import sys
n = int(sys.stdin.readline())
d = [] #dp 테이블
for i in range(n):
    d.append(list(map(int,sys.stdin.readline().split())))

for i in range(1,n):
    for j in range(0,i+1):
        #각 줄의 맨 처음과 끝은 전 + 자기 자신
        if j == 0:
            d[i][j] = d[i-1][j] + d[i][j]
        elif j == i:
            d[i][j] = d[i-1][j-1] + d[i][j]
        else: #양 사이드 제외한 수들은 더 큰 것을 선택해서 자기자신 더함
            d[i][j] = max(d[i-1][j-1],d[i-1][j]) + d[i][j]
print(max(d[n-1]))

풀이

다이나믹 프로그래밍이다.

입력받은 수를 배열에 넣고 이 배열을 dp테이블로 이용하여 합을 기록한다.

위부터 차례로 내려가며 왼쪽 오른쪽으로 이동하며 큰 값을 기록할 때,

양 사이드는 전 값 + 자기 자신이었고

양 사이드가 아닌 값들은 max(전 값) + 자기자신 이었다.

이를 코드로 바꾸면 된다.

import sys
n = int(sys.stdin.readline())
price = [0] + list(map(int,sys.stdin.readline().split()))
d = [0]*(n+1)

for i in range(1,n+1):
    for j in range(1,i+1):
        d[i] = max(price[j]+d[i-j], d[i])
print(d[n])

풀이

다이나믹 프로그래밍이다.

dp테이블인 d[i] 는 카드를 i개 샀을 때의 최대 값을 저장한다.

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

price[2] + d[i-1]

...

price[i] + d[0]

규칙을 찾아 점화식을 세운다.

d[n] = price[k] + d[n-k]

import sys
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
d = [arr[0]]
for i in range(0,n-1):
    d.append(max(d[i]+arr[i+1], arr[i+1]))
print(max(d))

풀이

다이나믹 프로그래밍으로 풀었다.

반복문을 돌면서 계속 더해간 값에 다음 값을 더한 값과 다음 값 중에 큰 값을 dp테이블에 넣는다.

최종적으로 dp테이블에서 max 값 출력한다.

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

import sys
n = int(sys.stdin.readline())
d = [0]*1001
d[1]=1
d[2]=3
for i in range(3,n+1):
    d[i] = (d[i-2]*2)+d[i-1]
print(d[n] % 10007)

풀이

다이나믹 프로그래밍이다.

d[1] = 1

d[2] = 3

d[3] = 5

d[4] = 11

...

규칙을 찾아 구현했다.