백준

문제 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 정답 소스코드 (Python) from collections import deque n,m=map(int,input().split()) field=[] for i in range(n):field.append(list(map(int,list(input())))) visited=[[[0 for k in range(2)] for i in range(m)]for j in range(n)] wall_break=0 dx=[0,0,1,-1] d..

문제 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 정답 소스코드 (Python) n=int(input()) arr=list(map(int,input().split())) arr.sort() count=0 for i in range(n): left,right=0,n-1 #기본 left, right설정 #반례 처리 N은 자기자신을 제외한 다른 수 이기 때문에 if i==0:left+=1 if i==n-1:right-=1 #투포인터 탐색 while leftarr[i]: right-=1 if right==i:right-=1 #반례 처리 N은..

문제 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 정답 소스코드 (Python) n,new,p=map(int,input().split()) if n==0:print(1) else: grade=list(map(int,input().split())) for i in range(len(grade),p):grade.append(-1) p_in=False rank=[1] for i in range(1,p): if grade[i]==grade[i-1]:rank.append(rank[i-1..

문제 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 정답 소스코드 (Python) cost=int(input()) cost=1000-cost result=0 def calculate(value): global cost,result if cost>=value: result+=cost//value cost-=value*(cost//value) for ele in [500,100,50,10,5,1]:calculate(ele) print(result) 풀이 (Python) 그리디 문제의 제일 ..

문제 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 정답 소스코드 (Python) n=int(input()) edge=list(map(int,input().split())) vert=list(map(int,input().split())) result=0 vert_min=min(vert) skip_point=0 for i in range(n): recent_cost=vert[i] if skip_point>i:continue if vert_min==recent_cost: edge_sum=0 for ..

문제 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 정답 소스코드 (Python) def dfs(vert,start): visited[vert]=True value=field[vert] if not visited[value]:dfs(value,start) elif visited[value] and value==start:result.append(value) n=int(input()) field=[0] result=[] for i in range(n):field.append(int(input())..

문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 정답 소스코드 (Python) import sys sentence=sys.stdin.readline().rstrip() bomb=sys.stdin.readline().rstrip() bomb_len=len(bomb) stack=[] for i in range(len(sentence)): stack.append(sentence[i]) if ''.join(stack[-bomb_len:])==bomb: for j in range(bomb_len):..

문제 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 정답 소스코드 (Python) import heapq v,e=map(int,input().split()) graph=[[]for _ in range(v+1)] dis=[1e9]*(v+1) for i in range(e): v1,v2,e=map(int,input().split()) graph[v1].append([v2,e]) graph[v2].append([v1,e]) def dijkstra(start): q=[] heapq.heappush(q,(0,start)) d..

문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 정답 소스코드 (Python) n,d=map(int,input().split()) shortcut=[] for i in range(n):shortcut.append(list(map(int,input().split()))) shortcut.sort() dp=[i for i in range(d+1)] k=0 for i in range(d+1): dp[i]=min(dp[i-1]+1,dp[i]) while k

문제 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 정답 소스코드 (Python) n=int(input()) arr=[] for _ in range(n):arr.append(int(input())) dp=[1]*(n+1) lenth=0 for i in range(n): for j in range(i): if arr[i]>arr[j]: if dp[i]