문제 링크https://www.acmicpc.net/problem/14950문제 설명서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재한다. 각각 도시는 1번부터 N번까지 번호가 붙여져 있다. 그 중에서 1번 도시의 군주 박건은 모든 도시를 정복하고 싶어한다.처음 점거하고 있는 도시는 1번 도시 뿐이다. 만약 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고 있어야 한다. 조건을 만족하는 도시 중에서 하나인 A를 선택하면, B를 정복하는 과정에서 A와 B를 연결하는 도로의 비용이 소모된다. 박건은 한번에 하나의 도시만 정복을 ..
문제 링크https://www.acmicpc.net/problem/1205문제 설명태수가 즐겨하는 디제이맥스 게임은 각각의 노래마다 랭킹 리스트가 있다. 이것은 매번 게임할 때 마다 얻는 점수가 비오름차순으로 저장되어 있는 것이다.이 랭킹 리스트의 등수는 보통 위에서부터 몇 번째 있는 점수인지로 결정한다. 하지만, 같은 점수가 있을 때는 그러한 점수의 등수 중에 가장 작은 등수가 된다.예를 들어 랭킹 리스트가 100, 90, 90, 80일 때 각각의 등수는 1, 2, 2, 4등이 된다랭킹 리스트에 올라 갈 수 있는 점수의 개수 P가 주어진다. 그리고 리스트에 있는 점수 N개가 비오름차순으로 주어지고, 태수의 새로운 점수가 주어진다. 이때, 태수의 새로운 점수가 랭킹 리스트에서 몇 등 하는지 구하는 프로그..
문제 링크https://www.acmicpc.net/problem/16437문제 설명N개의 섬으로 이루어진 나라가 있습니다. 섬들은 1번 섬부터 N번 섬까지 있습니다.1번 섬에는 구명보트만 있고 다른 섬에는 양들 또는 늑대들이 살고 있습니다.늘어나는 늑대의 개체 수를 감당할 수 없던 양들은 구명보트를 타고 늑대가 없는 나라로 이주하기로 했습니다.각 섬에서 1번 섬으로 가는 경로는 유일하며 i번 섬에는 pi번 섬으로 가는 다리가 있습니다. 양들은 1번 섬으로 가는 경로로 이동하며 늑대들은 원래 있는 섬에서 움직이지 않고 섬으로 들어온 양들을 잡아먹습니다. 늑대는 날렵하기 때문에 섬에 들어온 양을 항상 잡을 수 있습니다. 그리고 늑대 한 마리는 최대 한 마리의 양만 잡아먹습니다.얼마나 많은 양이 1번 섬에 ..
문제 링크https://www.acmicpc.net/problem/11568문제 설명민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 정해진 순서대로 보여줄 것이다. 준민이는 앞의 카드부터 임의의 개수만큼 골라서 민균이에게 제시하게 되는데, 제시한 카드의 수열이 순증가가 아니면 민균이에게 바보라고 놀림받게 된다. 예를 들어 민균이가 보여준 카드가 {4, 9, 10, 9} 일 때 준민이가 {4, 9}를 골랐다면 놀림을 받지 않겠지만, {4, 10, 9}이나 {9, 9}를 제시하면 놀림받게 될 것이다.생각보다 바보가 아닌 준민이는 한번도 민균이에게 놀림을 받지 않았다. 이에..
문제 링크https://www.acmicpc.net/problem/2698 문제 설명0과 1로 이루어진 수열 S가 있다. S의 첫 수는 s1이고, 마지막 수는 sn이다. S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.s1*s2 + s2*s3 + s3*s4 + … + sn-1 * sn위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.예를 들어, n이 5이고, k가 2이면, 수열 S가 될 수 있는 수열은 다음과 같이 6가지가 있다.11100, 01110..
문제 링크https://www.acmicpc.net/problem/16928문제 설명뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 ..
문제 링크https://www.acmicpc.net/problem/12906문제 설명오늘은 새로운 하노이 탑 게임을 해보려고 한다. 이 게임의 규칙은 다음과 같다.막대는 총 세 가지 종류가 있다. 막대 A, 막대 B, 막대 C게임이 시작될 때, 각각의 막대에는 0개 또는 그 이상의 원판이 놓여져 있다.모든 원판의 크기는 같으며, 원판의 종류도 A, B, C로 세 가지가 있다. 원판은 원판 A, 원판 B, 원판 C와 같이 표현한다.한 번 움직이는 것은 한 막대의 가장 위에 있는 원판을 다른 막대의 가장 위로 옮기는 것이다.게임의 목표는 막대 A에는 원판 A만, 막대 B는 원판 B만, 막대 C는 원판 C만 놓여져 있어야 한다.되도록 최소로 움직여야 한다.막대 A, 막대 B, 막대 C에 놓여져 있는 원판의 상..
문제 링크https://www.acmicpc.net/problem/16987문제 설명원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱걸이를 5회 하는 기적의 운동 루틴을 통해 뇌와 근육을 동시에 단련한다. 근육을 단련할 때 식단이 정말로 중요하다는 것을 아는 인범이는 탄수화물이 많은 밥이나 빵 따위의 아침 식사를 대신해 단백질이 많은 계란찜을 해먹는다. 계란찜을 먹기 위해서는 계란을 깨야 하는데, 인범이는 힘이 너무 넘치는 나머지 부엌의 대리석을 이용해 계란을 깨면 늘 껍데기가 산산조각나 뒷처리가 너무 어렵게 되곤 한다. 어떻게 하면 계란을 조심스럽게 깰 수..
