넘치게 채우기

https://www.acmicpc.net/problem/14926 BOJ - Not Equal문제 유형: 오일러 경로, 그래프, dfs, 그리디, 백트래킹문제 난이도: Gold V시간 제한: 1초메모리 제한: 512MB 문제주어진 N개의 수가 모두 서로 다르다는 것은 기호 "!="를 통해 하나의 식으로 표현할 수 있다. 예를 들어 A, B, C가 모두 서로 다르다는 것은 논리식으로 (A != B) && (B != C) && (C != A) 로 쓸 수 있고, 이를 다음과 같이 한 줄로 표현하는 것을 A, B, C에 대한 "한 줄 표기법"이라고 부르기로 하자.A != B != C != A하지만 5개의 수 A, B, C, D, E가 모두 서로 다르다는 것을 다음처럼 표현하는 것은 올바른 한 줄 표기법이 아니..

https://www.acmicpc.net/problem/1507BOJ - 궁금한 민호문제 유형: 그래프, 최단경로, 플로이드-워셜문제 난이도: Gold II시간 제한: 2초메모리 제한: 128MB 문제강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.예를 들어, 예제의 ..

https://www.acmicpc.net/problem/17501BOJ - 수식 트리문제 유형: 트리, 그래프, 그리디, 정렬문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다.연산자 노드는 항상 두 개의 자식 노드를 가지며 연산자로 '+' 또는 '-' 를 가집니다.피연산자 노드는 아무 자식도 가지지 않고 하나의 정수를 가집니다.수식 트리의 계산은 다음과 같이 진행됩니다.2개의 피연산자 노드를 자식으로 가지는 연산자 노드를 하나 선택합니다.해당 노드의 연산자가 '+' 인 경우, 연산자 노드를 피연산자 노드로 바꾸고 ..

https://www.acmicpc.net/problem/18231BOJ - 파괴된 도시문제 유형: 해 구성하기, 그래프 이론문제 난이도: Gold V시간 제한: 2초메모리 제한: 512MB 문제저명한 역사학자 지수는 오래된 지도 한 장을 주웠다. 이 지도는 N개의 도시와 M개의 도로로 이루어져 있으며, 각 도시는 1부터 N까지 하나씩 번호가 매겨져있다. 지도에는 불에 탄 모습의 K개의 도시가 있었는데, 지수는 이 지도가 전쟁 당시 파괴된 도시를 표시한 지도임을 알아차렸다. 연구한 바에 의하면, 어떤 도시에 그 당시 사용했던 폭탄을 떨어뜨리면 이 도시를 포함하여 인접한 도시들은 전부 파괴된다고 한다.지수는 이 사실을 토대로 당시 폭탄이 떨어진 지점들을 알아내기 위해 우리를 초대했다. 우리는 폭탄이 떨어진..

https://codeforces.com/contest/2067/problem/DCodeforces Round 1004(Div.2)] - D. Obejct Identification문제 유형: 그래프, 생성형, 인터랙티브시간 제한: 2초메모리 제한: 256MB 문제This is an interactive problem.You are given an array x1,…,xn">x1,…,xn of integers from 1">1 to n">n. The jury also has a fixed but hidden array y1,…,yn">y1,…,yn of integers from 1">1 to n">n. The elements of array y">y are unknown to y..

https://www.acmicpc.net/problem/2644BOJ - 촌수계산문제 유형: bfs, 최단경로문제 난이도: Silver II시간 제한: 1초메모리 제한: 128MB 문제우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력사람들은 1, ..

https://www.acmicpc.net/problem/2583BOJ - 영역 구하기문제 유형: dfs, bfs, 그래프문제 난이도: Silver I시간 제한: 1초메모리 제한: 128MB 문제눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다.와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머..

https://www.acmicpc.net/problem/7562BOJ - 나이트의 이동문제 유형: bfs, 그래프, 최단 경로문제 난이도: Silver I시간 제한: 1초메모리 제한: 256MB 문제체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘..

https://www.acmicpc.net/problem/2887BOJ - 행성 터널문제 유형: MST(최소 신장 트리), 최단 경로, 그래프, 정렬, 이진 탐색문제 난이도: Platinum V시간 제한: 1초메모리 제한: 128MB 문제때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모..

https://www.acmicpc.net/problem/13460BOJ - 구슬 탈출 2문제 유형: bfs, 시뮬레이션, 그래프문제 난이도: Gold I시간 제한: 2초메모리 제한: 512MB 문제스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 ..