은하철도999

5014번: 스타트링크 (acmicpc.net) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net from queue import Queue F,S,G,U,D = map(int,input().split()) def bfs(): q = Queue() q.put(S) visited = [-1]*(F+1) visited[S]=0 while q.qsize()!=0: x = q.get() if x==G: #목표 층이면 return visited[x] for i in (x-D, x+U): if 0

17086번: 아기 상어 2 (acmicpc.net) 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 문제 해석 아기 상어와 가장 거리가 먼 칸과의 거리 구하기 - 8방향으로 이동할 수 있다. 풀이 방법 BFS 사용 처음에는 각 칸마다 상어를 만나기 전까지 BFS를 돌려 안전 거리를 구하였는데 시간초과가 발생.. -> 상어가 있는 곳만 BFS로 돌림 상어가 있는 위치를 미리 queue에 담아놓고 8방향으로 방문하여 queue에 담아준다. 아직 방문하지 않은 칸에 상어와 떨어진 거리를..

2304번: 창고 다각형 (acmicpc.net) 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제 해석 기둥을 모두 둘러싼 가장 작은 도형의 넓이 구하기 [조건] 지붕이 파인 모양이 있으면 안 됨 -> 중간에 작은 기둥을 만나도 건물의 높이는 내려가면 안 됨 접근 방법 가장 높은 기둥으르 기준으로 왼쪽과 오른쪽을 나눈다. -> 낮은 쪽으로 갈 일을 고려하지 않아도 되기 때문에 - 왼쪽은 왼쪽부터 가장 높은 기둥으로 접근 - 오른쪽은 오른쪽부터 가장 높은 기둥으로 접근 나보다 높은 애를 만..

2493번: 탑 (acmicpc.net) 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 해석 접근 방법 stack을 사용 stack은 후입선출의 구조이기 때문에 stack에서 하나씩 꺼낼 때마다 가장 가까운 탑이랑 비교할 수 있음 (왼쪽에서 진행하기 때문에 나의 왼쪽에 있는 탑만 stack에 들어감) stack에 탑의 index를 넣음 - stack의 마지막에 쌓인 탑의 길이가 나보다 높다면 출력, 내 탑을 넣음 - stack의 마지막에 쌓인 탑의 길이가 나보다 높지 않다면 stack에서 하나 빼고 ..

23253번: 자료구조는 정말 최고야 (acmicpc.net) 23253번: 자료구조는 정말 최고야 위 그림처럼 책이 쌓여 있으므로, 첫 번째 더미 - 두 번째 더미 - 첫 번째 더미 - 두 번째 더미 순으로 꺼내면 책 번호순으로 나열할 수 있다. www.acmicpc.net 문제 해석 쌓여진 책 더미를 순서대로 하나로 쌓을 수 있는가 접근 방법 마지막에 쌓여진 책보다 밑에 있는 책의 번호가 작으면 결코 순서대로 책을 빼낼 수 없다. -> 입력받은 책 더미들이 역순으로 정렬되어 있는지 확인 **input()으로 입력 받으면 시간초과 => sys.stdin.readline() 사용 import sys n,m = map(int,sys.stdin.readline().split()) for i in range(..

15903번: 카드 합체 놀이 (acmicpc.net) 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 문제 해석 가지고 있는 카드 중 두개의 수를 골라 합을 구한 후, 두 카드의 숫자를 합으로 바꾼다. 이때, 모든 카드의 합이 최소가 되게 하라 접근 방법 가장 작은 두 수의 합으로 카드를 덮어씌어야 한다. -> 정렬을 이용해 첫번째 카드와 두번째 카드를 고른다. -> sort() 함수 이용 N,m = map(int,input().split()) card=list(map(i..

1976번: 여행 가자 (acmicpc.net) 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 해석 여행 경로와 도시의 연결 정보가 주어질 때, 여행 경로가 유효한 것인지 확인 [조건] 방문한 도시를 다시 방문해도 된다. 접근 방법 **방향은 중요하지 않고 노드들 끼리 연결되어 있으면 됨** [BFS] 방문을 원하는 노드중 첫번째 것을 선택 첫번째 노드에서 갈 수 있는 모든 노드로 다 접근 (아직 방문하지 않았고 연결되어 있다면) 방문한 노드는 따로 체크되었기 때문에 -> 여행 경로에 해당하는 노드들 ..