say repository

import sys

a,b,v = map(int,sys.stdin.readline().split())
day = 0
h = 0
while True:
    day += 1
    h += a
    if h == v:
        print(day)
        break
    h -= b

코드 

import sys
import math
a,b,v = map(int,sys.stdin.readline().split())

day = (v-b)/(a-b)
print(math.ceil(day))

풀이

(a-b) 씩 day가 증가하고 day == v 가 됐을 때가 정답이다.

하지만, 정상에 오르면 밤에 미끄러지지 않기 때문에, 

v / (a-b) 가 아니고 (v-b) / (a-b) 이다.

import sys
k,n = map(int,sys.stdin.readline().split())
arr = []
for i in range(k):
    arr.append(int(sys.stdin.readline()))
start = 1
end = max(arr)
while (start<=end):
    total = 0
    mid = (start+end)//2
    for i in arr:
        total += i//mid
    if total >= n:
        start = mid + 1
    else:
        end = mid -1
print(end)

풀이

파라메트릭 서치 ( Parametric Search)

: 최적화 문제를 결정 문제( yes or no)로 바꾸어 해결하는 기법

: 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제

-> 이분 탐색 방법으로 푼다. ( 재귀 말고 반복문 사용 )

start = 1

end = max(arr)

mid = (start + end)//2

start가 end가 될 때까지, mid값을 조절하여 답(end값)을 구한다.

코드

import sys
n = int(sys.stdin.readline())
rgb = []
for _ in range(n):
    rgb.append(list(map(int,sys.stdin.readline().split())))

for i in range(1,n):
    #R
    rgb[i][0] = min(rgb[i-1][1], rgb[i-1][2]) + rgb[i][0]
    #G
    rgb[i][1] = min(rgb[i-1][0], rgb[i-1][2]) + rgb[i][1]
    #B
    rgb[i][2] = min(rgb[i-1][0], rgb[i-1][1]) + rgb[i][2]
print(min(rgb[n-1]))

풀이

빨강, 초록, 파랑 순으로 집 비용이 있다.

조건을 따지고 보면 전 집의 색을 제외한 다른 색 중 가장 작은 비용의 색으로 칠하면 된다.

index 가 0은 제외하고

1부터 반복문을 색별로 돌면 된다.

#R
rgb[i][0] = min(rgb[i-1][1], rgb[i-1][2]) + rgb[i][0]

설명해보면, i가 1이라고 해보자.

rgb[1][0] 1번집의 빨간색으로 칠하는 비용은, 전 집인 0번째 집은 빨간색으로 칠하면 안된다. 

0번째 집의 비용은 초록 rgb[0][1], 파랑 rgb[0][2] 중 작은 비용을 선택하고 현재 1번집의 빨간색 비용을 더한 값이 rgb[1][0] 이 되겠다.

코드

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(전 값) + 자기자신 이었다.

이를 코드로 바꾸면 된다.