say repository

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int,input().split()) #간선, 노드
start = int(input()) #시작노드
#각 노드에 연결되어 있는 노드에 대한 정보 리스트
graph = [[] for _ in range(n+1)]
distance = [INF]*(n+1)
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))  #노드 a에서 노드 b로 가는 비용이 c라는 의미

#다익스트라
def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q:
        #우선순위 큐에서 가장 최단 거리가 짧은 노드 꺼내기
        dist,node = heapq.heappop(q)
        #현재 노드가 이미 처리된 노드면 무시
        if distance[node] < dist:
            continue
        #현재 노드와 연결된 다른 인접한 노드들 확인
        for i in graph[node]:
            #현재 노드를 거쳐서 다른 노드로 이동하는 거리
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
dijkstra(start)

#모든 노드로 가는 최단거리 출력
for i in range(1,n+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

풀이

최단경로 다익스트라 알고리즘이다.

다익스트라 알고리즘은 그리디 알고리즘에 속한다.

우선순위 큐를 사용해 출발 노드의 인근 노드의 최소 비용을 구해 최단 거리로 이동한다.

python에서의 우선순위 큐는 heapq 라이브러리를 사용해 구현한다.

heapq는 최소힙이 디폴트다.

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 해준다.

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