차곡차곡

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 정답 code #특정한 최단 경로 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start): visit = [INF]*(n+1) q = [] heapq.heappush(q,(0,start)) visit[start] = 0 while q: dis, node =..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 정답 code #파티 import heapq import sys input = sys.stdin.readline INF = int(1e9) #무한 설정 n,m,x = map(int,input().split()) road = [[] for _ in range(n+1)] for _ in range(m): s,e,time = map(int,input().split()) r..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 정답 code #트리의 지름 from collections import deque import sys input = sys.stdin.readline def bfs(s): queue = deque() visit = [-1] * (v+1) queue.append(s) visit[s] = 0 node_distance = [0,0] while queue: q = queue.popleft..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 정답 code #RGB거리 import sys input = sys.stdin.readline n = int(input()) cost = [] for _ in range(n): r,g,b = map(int,input().split()) cost.append([r,g,b]) for i in range(1,n): cost[i][0] = min(cost[i-1][1],cost[i-..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 정답 code #거짓말 import sys input = sys.stdin.readline n,m = map(int,input().split()) know = set(input().split()[1:]) party = [] for _ in range(m): party.append(set(input().split()[1:])) #매 파티마다 진실을 알게되는 사람이 생김으로 파티 수만큼 반복 for _ in r..

정답 code #Four Squares import sys def check(n): # n의 제곱근이 정수라면 1출력 if (n**0.5).is_integer() : return 1 # n보다 작은 어떤 수를 뺀 수의 제곱근이 정수라면 2출력 ex(A^2+B^2) for i in range(1, int(n**0.5)+1): if (int(n-i*i)**0.5).is_integer(): return 2 #n보다 작은 어떤 제곱근의 수를 두개뺀 수의 제곱근이 정수라면 3출력 ex(A^2+B^2+C^3) for i in range(1,int(n**0.5)+1): for j in range(1, int((n-i*i)**0.5)+1) : if ((n-(i*i)-(j*j))**0.5).is_integer(): re..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 정답 code #비밀번호 찾기 import sys input = sys.stdin.readline n,m = map(int,input().split()) potal = {} for i in range(n): site,password = input().split() potal[site] = password for i in range(m): target = input()..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 정답 code #뱀과 사다리 게임 from collections import deque import sys input = sys.stdin.readline def bfs(v): queue = deque() queue.append(v) visit[v] = 1 while queue: target = queue.popleft() for i in range(..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 정답 code #아기 상어 from collections import deque import sys input = sys.stdin.readline dx = [-1,1,0,0] dy = [0,0,1,-1] def bfs(x,y,shark_size): distance = [[0]*n for _ in range(n)] #거리 저장 visit = [[0]*n for _ in range(n)] #..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 정답 code #테트로미노 import sys input = sys.stdin.readline def dfs(r,c,bcount,total): global ans #종료조건1 - 최댓값에 못미치는 경우 if ans >= total + max_value * (3-bcount): return #종료조건2 - 블럭 4개를 모두 활용한 경우 if bcount == 4: ans = max(ans, tota..