문제 링크https://www.acmicpc.net/problem/31502  문제토카는 어쩌다 마주친 아름다운 한별 선배에게 마음을 빼앗겨 버리고 말았다! 말을 걸고 싶었지만 그럴 자신이 없었던 토카는 한별 선배에게 말을 걸 만한 명분을 찾기 시작했다. 평소에 만화를 많이 읽던 토카는 그 명분을 만들 방법을 한 만화책에서 찾아냈다! 만화 속 남자 주인공과 여자 주인공이 등굣길에 벚꽃 아래에서 서로 부딪혔던 사건을 계기로 친해졌다는 내용을 보고 직접 따라 하기로 결심했다.토카네 동네에는 벚나무가 없기 때문에 대신 은행나무가 있는 곳에서 시도하고자 한다. 토카네 동네는 1부터 N까지의 번호가 붙은 N개의 은행나무와 양 끝에 은행나무가 심어진 M개의 도로로 구성되어 있다. 모든 도로는 양방향 이동이 가능하며..

문제 링크https://www.acmicpc.net/problem/1584 문제세준이는 위험한 지역에서 탈출하는 게임을 하고 있다. 이 게임에는 세준이가 들어갈 수 없는 죽음의 구역이 있고, 들어가서 한 번 움직일 때 마다 생명이 1씩 소모되는 위험한 구역이 있다. 그리고, 자유롭게 생명의 위협없이 움직일 수 있는 안전한 구역이 있다. (안전한 구역은 죽음의 구역과 위험한 구역을 제외한 나머지 이다.)세준이는 (0, 0)에서 출발해서 (500, 500)으로 가야 한다. 세준이는 위, 아래, 오른쪽, 왼쪽으로만 이동할 수 있다. 현재 세준이는 (0, 0)에 있다. 그리고, 게임 판을 벗어날 수는 없다.세준이가 (0, 0)에서 (500, 500)으로 갈 때 잃는 생명의 최솟값을 구하는 프로그램을 작성하시오...

문제 링크https://www.acmicpc.net/problem/20008 문제가장 빠른 시간 내에 몬스터를 처치하려고 한다. 사용할 수 있는 스킬은 N개 있으며, 각 스킬은 사용하는 데 1초가 들고, 사용을 시작한 지 1초 후 몬스터에게 일정 대미지를 입힌다. 여러 개의 스킬을 동시에 사용할 수는 없다.각 스킬에는 저마다의 대기 시간과 대미지가 있다. 대기 시간은 스킬을 사용하기 시작한 순간부터 차기 시작한다.예를 들어, 현재 시각이 t = 0이고, 대기 시간이 10초이고 대미지가 10인 스킬을 체력이 100인 몬스터에게 사용했다고 하자. 그러면 t = 1일 때 몬스터의 체력이 90으로 줄어들고, 같은 스킬은 t = 10일 때부터 다시 사용할 수 있다. 입력첫 번째 줄에는 스킬 개수 N(1 ≤ N ≤..

문제 링크https://www.acmicpc.net/problem/16991 문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 모든 도시 사이에는 길이 있다. 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있..

문제 링크https://www.acmicpc.net/problem/2098 문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러..

문제 링크https://www.acmicpc.net/problem/21939 문제tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다.깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다.만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다. recommend x x가 1인 경우 추천 문제 리스트에서 가장 어려운 문제의 번호를 출력한다.만약 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것으로 출력한다. x가 -1인 경우 추천 문제 리스트에서 가장 쉬운 문제의 번호를 출력한다.만약 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력한다.add P L추천 문제 리스트에 난이도가 L인 문제 번호 P를 추가..

문제 링크https://www.acmicpc.net/problem/5594 문제あなたは JOI 新聞社の記者であり，スポーツ記事を担当している．昨日までに，クロアチアでは，n 個のサッカーチームによる総当りのリーグ戦が 行われた．大会実行委員会は，試合結果と規定に基づき各チームに 1 位から n 位ま での順位をつけたようである．あなたには，一部の試合の勝敗とともに，次の情報 が伝えられた．情報 1 引き分けの試合はなかった．情報 2 全てのチームに異なる順位がついた．情報 3 全ての 1 ≤ a  あなたは記事を作成するために，一部の試合の勝敗と，伝えられた情報 1～3 をも とに，順位表を推測することにした．入力として一部の試合の勝敗が与えられたとき，伝えられた情報に適合する順位 表を 1 つ出力するプログラムを作れ．また，出力した順位表以外に，伝えられた情 報に適合する..

문제 링크https://www.acmicpc.net/problem/5021 문제유토피아의 왕이 사망했다. 왕은 자손을 남기지 않고 사망했기 때문에, 왕위를 계승할 사람을 지목하지 않았다. 왕실 귀족은 왕위를 주장하기 시작했다. 유토피아의 법에는 왕의 계승자가 없는 경우에, 나라를 세운 사람과 혈통이 가까운 사람이 유토피아를 통치한다는 조항이 있다.나라를 세운 사람과 혈통이 가장 가까운 사람은 그의 자손이 아닌 사람과 피가 덜 섞인 사람이다. 모든 사람은 아버지의 혈통과 어머니의 혈통을 반 씩 받게 된다. 나라를 세운 사람의 자식은 1/2 왕족이며, 그 아들이 왕족이 아닌 사람과 결혼한 경우에는 아들의 자식은 1/4 왕족이 된다.가장 나라를 세운 사람과 혈통이 가까운 사람을 찾는 프로그램을 작성하시오.  ..

문제 링크https://www.acmicpc.net/problem/31423 문제극단적인 출산율 감소로 인해 신촌 지역 N개 대학교가 하나의 학교로 통합되었다.기나긴 회의 끝에, 통합된 학교의 이름은 N개 대학교의 이름을 이어 붙여서 정해졌다. 회의에서 통합된 학교의 이름을 정한 방법은 다음과 같다. N개 대학교의 이름 s1, s2, ⋯, sN을 일렬로 나열한다. 이후 다음의 과정을 N − 1번 반복한다. si, sj가 빈 문자열이 아닌 서로 다른 두 정수 i, j를 고른다. si의 뒤쪽에 sj를 이어 붙인다. sj를 빈 문자열로 바꾼다.모든 과정이 끝난 뒤에는 빈 문자열이 아닌 sk가 하나 남게 되며, 이때 sk가 통합된 학교의 이름이 된다. N개 대학교의 이름 s1, s2, ⋯, sN과 회의에서 고른..

문제 링크https://www.acmicpc.net/problem/32360 문제한여름의 날씨는 더워도 너무 덥다. 민규는 외출은커녕 집에서 에어컨에 의지한 채 살아가고 있지만, 오늘은 약속이 있어 불가피하게 집 밖으로 나와 약속 장소로 가야 한다. 그러나 시원한 집에서 쉬다 보니 어느새 약속 시간에 늦어버리고 말았다. 빨리 집을 나서야 한다!밖은 N행 M열의 격자로 이루어져 있다. 격자의 각 칸은 집, 약속 장소, 건물, 벽, 길 중 하나로 이루어져 있다. 집과 건물은 실내이고, 길, 벽, 약속 장소는 실외이다.밖은 너무 더워 실외에 있을 때는 지속적으로 불쾌함 B가 증가한다. 그러나 중간중간 이동 경로에 있는 실내는 매우 시원하여, 실내를 지나가거나 실내에서 쉬는 동안에는 불쾌함이 감소한다.초기에 민..

문제 링크https://www.acmicpc.net/problem/32197 문제지하철의 전기를 공급받는 방식(급전 방식)은 직류와 교류로 구분된다. 열차 운행 중 급전 방식이 바뀌게 되면 잠시 전력 공급이 중단된다. 이러한 현상을 절연이라 부른다. 열차 탑승객의 만족도는 절연이 적게 발생할수록 높아진다.서울특별시에는 N개의 지하철역이 있고, 두 역을 직접 잇는 선로 M개가 설치되어 있다. 각 역에는 1부터 N번까지의 번호가, 선로에는 1부터 M번까지의 번호가 붙어있다. 설치되어 있는 선로만으로 임의의 두 역 사이를 이동할 수 있다. 각 선로는 직류 또는 교류 중 하나의 방식으로 전기를 공급하며 양방향으로 통행할 수 있다.열차는 어떤 역과 이어진 선로를 통해 다른 역으로 이동하는 과정을 몇 번이든 반복할..

문제 링크https://www.acmicpc.net/problem/2352 문제반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다. 예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오 입력첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …,..

문제 링크https://www.acmicpc.net/problem/2550  문제N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 번호의 스위치와 전구는 전선으로 서로 연결되어 있다.  하나의 스위치를 누르면 그 스위치와 연결된 전구에 불이 들어오게 된다. 두 개 이상의 스위치를 같이 누르는 경우, 전선이 서로 만나면 만난 전선에 연결된 전구들의 불은 켜지지 않는다.위 그림에서 1번과 4번의 스위치를 같이 누르면 1번과 4번의 전구에는 불이 켜지지만, 1번과 2번의 스위치를 같이 누르면 1번과 2번 전구의 불은 켜지지 않는다. 1번과 3번 그리고 5번 스위치를 같이..

문제 링크https://www.acmicpc.net/problem/12738 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 예제 입력 1610 20 10 30 20 50예제 출력 14 알고리즘 분류다이나믹 프로..

문제 링크https://www.acmicpc.net/problem/23563 문제루시우는 높이가 H이고 너비가 W인 맵의 시작점에서 끝점까지 이동하려고 한다.맵은 H개의 행과 W개의 열로 이루어진 격자판 모양이다. 각 칸은 벽 또는 빈칸이다.루시우는 상, 하, 좌, 우 방향 인접한 칸으로 한 칸씩 이동할 수 있다. 벽으로는 이동할 수 없다.루시우가 한 칸을 이동하는 데에는 1초가 걸린다.하지만 루시우가 벽을 타고 이동하면 순식간에 (0초의 시간에) 상, 하, 좌, 우 방향 인접한 칸으로 이동할 수 있다.어떤 빈칸의 상하좌우 중 하나가 벽이면 이 칸은 벽에 인접한 칸이라고 한다.벽에 인접한 칸에서 벽에 인접한 칸으로 이동하면 벽을 타고 이동한다고 말한다. 루시우가 맵의 시작점에서 끝점까지 이동하는 데 걸리..