![]()
문제 https://www.acmicpc.net/problem/5972 풀이 택배 배송 문제, 여물을 헛간인 1에서 헛간 N으로 배달하는 것은 여러가지 그래프를 활용하여 풀 수 있다. 그중 가는 길의 길이는 고려하지 않으므로, 다익스트라를 활용하여 풀 수 있다. 입력에 대한 그래프를 구성하는 과정에서, 해당 문제는 간선에 대해 방향을 따지지 않는 무향 그래프 이므로, 입력 시에 양쪽 출력 노드에 대해 값을 추가해주어야 한다. 코드 import heapq INF = int(1e9) N,M = map(int, input().split()) graph = [[] * (N+1) for _ in range(N+1)] distance = [INF] * (N+1) for _ in range(M): a,b,c = ma..
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 ..
0. 문제 https://www.acmicpc.net/problem/29687 29687번: Игра Два игрока играют в новую настольную игру. На поле для игры есть города и дороги между ними, причем дороги между разными городами могут имет www.acmicpc.net 문제 해석 두 명의 플레이어가 새로운 보드 게임을 하고 있습니다. 경기장에는 도시와 도시 사이에 도로가 있으며, 도시마다 도로의 길이가 다를 수 있습니다. 또한 두 도시 사이의 도로 길이가 x라면 이 도로에는 (x-1)개의 마을이 연속적으로 있으므로 도시에서 도로의 가장 바깥쪽 마을로, 이 마을에서 이웃 마을로 갈 수 있습니다...
![]()
https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제 코드 import sys from collections import deque def bfs(x): queue = deque([x]) visited[x] = 1 cnt = 0 while queue: queue.popleft() for i in range(1, n + 1): if visited[i] == 0: queue.append(i) visited[i]..
![]()
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 너비 우선 탐색을 이용하여 구현한다. 최소 날짜를 저장할 cnt, 안 익은 토마토 수를 저장할 zero, 익은 토마토의 위치를 저장할 q를 정의한다. 이중 반복문을 통해 익은 토마토라면 q에 append 하고, 안 익은 토마토의 개수를 확인한다. 만약 안 익은 토마토가 없다면 0을 출력한다. 만약 안 익은 토마토가 있다면 dfs를 수행한다. - q가 빌 때까지 반복한다...
문제 https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 코드 #include #include #include #include #include using namespace std; int main() { deque dq; deque dqw; int n = 0; cin >> n; for (int i = 0; i 2) { int f = 0; while (dq.size() != 2) { dqw.push_back(dq.front()); dq.pop_fro..
[문제] https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net [소스코드] T = int(input()) for _ in range(T): N, M = map(int, input().split()) sizes_A = list(map(int, input().split())) sizes_B = list(map(int, input().split())) sizes_A.sort() sizes_B.sort()..
![]()
https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 시뮬레이션 너비 우선 탐색 문제 뿌요뿌요의 룰은 다음과 같다. 필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다. 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된..
![]()
1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 코드 import sys input = sys.stdin.readline dx= [0,0,1,-1] dy= [1,-1,0,0] t = int(input()) for _ in range(t): m,n,k=map(int,input().split()) #가로세로 배추개수 qocn=[[0]*(m+2) for i in range(n+2)] #배추밭배추위치 visitdi = {} #전체적으로이미방문했나 ans=0 for i in ran..
https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 문제 올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다. 금메달 수가 더 많은 나라 금메달 수가 같으면, 은메달 수가 더 ..
![]()
문제 설명 미로를 탈출하는 최단 거리를 구하는 문제이다. 최단 거리를 구해야 하기에 깊이 우선 탐색이 아닌 너비 우선 탐색을 사용하였고, 입력이 붙어서 들어오기에 먼저 string으로 받고 인덱스 하나 하나 집어 넣어주었다. bfs를 도는 중에는 상하좌우를 검사하여 인덱스를 벗어나지 않고/방문하지 않았고/이동할 수 있는 위치일 때 큐에 삽입하였다. 그리고 처음 알았는데 queue.push 대신 queue.emplace를 쓰면 속도도 더 빠르고 pair같은 구조체를 make_pair를 사용하지 않고 바로 집어 넣을 수 있어 편했다. 최단 거리를 구하는게 조금 어려웠는데, 그냥 2차원 배열을 새로 만들어서 기록해주는게 제일 편한듯 했다. 코드 #include using namespace std; int N,..
![]()
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 코드 import sys input = sys.stdin.readline n = int(input()) check = list() y = 1 count = list() flag = 0 for _ in range(n): num = int(input()) while y
