차곡차곡

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 정답 code #벽부스고 이동하기 from collections import deque dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(x,y,z): queue = deque() queue.append((x,y,z)) while queue: a,b,c = queue.popleft() #끝에 도달한경우 결과값 반환 if a == n-1 and b ==..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 정답 code #내려가기 import sys input = sys.stdin.readline n = int(input()) score = list(map(int,input().split())) maxdp = score mindp = score for _ in range(n-1): a,b,c = map(int,input().split()) maxdp = [a+max(maxdp[0], maxdp[1]), b+max..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 정답 code #정수 삼각형 import sys input = sys.stdin.readline n = int(input()) t = [] for _ in range(n): num = list(map(int,input().split())) t.append(num) for i in range(1,n): # 층수 (0층은 한개의 값) for j in range(i+1): #가로줄 선택 (층수+1)개만큼 존재 # 가장 왼쪽 값일때 위의 값 if j == 0: t[i][j] ..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 정답 code # 후위 표기식 pn = input() stack = [] res = '' #결과값 저장 for p in pn: #알파벳일때, 결과값에 추가 if p.isalpha(): res += p else: # ( 일때 if p =='(': stack.append(p) # *, / 인경우 같은 우선순위인 *, / 가 있으면 결과값에 추가 elif p == '*' or p == '/': wh..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 정답 code # 최소비용 구하기 import heapq import sys input = sys.stdin.readline INT = int(1e9) def dijkstra(start): q = [] heapq.heappush(q,(0,start)) visit = [INT] * (n+1) visit[start] = 0 while q: dist, node = he..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 정답 code #웜홀 import sys input = sys.stdin.readline INF = int(1e9) def bellma_ford(start): visit = [INF]*(n+1) visit[start] = 0 #정점 개수만큼 반복 for i in range(n): for j in range(1,n+1): for next_node , time in roads[j]: #다..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 정답 code #최단경로 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start): q = [] heapq.heappush(q,(0,start)) visit = [INF] * (v+1) visit[start] = 0 while q: dist , node = heap..

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 =..

정답 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()..