처누

https://www.acmicpc.net/problem/2585문제 : 골드 2경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때, 경비행기의 연료통의 크기를 정하는 것이 중요한 문제가 된다. 큰 연료통을 장착하면 중간에 내려서 급유를 받는 횟수가 적은 장점이 있지만 연료통의 무게로 인하여 속도가 느려지고, 안정성에도 문제가 있을 수 있다. 한편 작은 연료통을 장착하면 비행기의 속도가 빨라지는 장점이 있지만 중간에 내려서 급유를 받아야 하는 횟수가 많아지는 단점이 있다. 문제는 중간에 내려서 급유를 받는 횟수가 k이하 일 때 연료통의 최소용량을 구하는 것이다. 아래 예를 보자.위 그림은 S, T와 7개의 중간 비행장의 위치를 나타내고 있는 그림이다. 위 예..

https://www.acmicpc.net/problem/2461문제 : 골드 2KOI 중학교에는 N개의 학급이 있으며, 각 학급의 학생 수는 모두 M명으로 구성된다. 이 중학교에서는 체육대회에 새로운 종목의 경기를 추가하였다. 이 경기에 대해 모든 학생들은 저마다의 능력을 나타내는 능력치를 가지고 있으며, 이 능력치는 모든 학생이 서로 다르다.이 경기는 한반에서 한 명의 대표선수를 선발하여 치른다. 경기의 형평성을 위하여, 각각의 반에서 대표로 선발된 모든 학생들의 능력치 중 최댓값과 최솟값의 차이가 최소가 되도록 선수를 선발하려고 한다. 예를 들어, N=3, M=4인 경우 학생들의 능력치가 1반=[12, 16, 67, 43], 2반=[7, 17, 68, 48], 3반=[14, 15, 77, 54]로..

https://www.acmicpc.net/problem/9460문제 : 골드 1매우 드물고 비싼 금속을 지하에서 찾아냈다. 금속은 땅 속에 넓게 흩어져 있기 때문에 신중하게 채굴 계획을 세우려고 한다. 따라서, 그림 1과 같이 수직 엘리베이터(vertical elevator)로 연결된 여러 개의 수평 터널(horizontal tunnel)을 만들기로 했다. 모든 엘리베이터는 한 터널의 오른쪽 끝과 다른 터널의 왼쪽 끝을 연결한다. 또, 터널과 엘리베이터의 연결 구조는 땅에 대해서 단조로워야 한다. 즉, 가장 왼쪽에 있는 터널의 끝에서 시작해서 가장 오른족에 있는 터널의 끝에 이동할 때, 다시 왼쪽으로 이동하는 일 없이 모든 터널을 지날 수 있어야 한다.예산이 제한되어 있기 때문에, 수평 터널을 k개만..

https://www.acmicpc.net/problem/18430문제 : 골드 4공학자 길동이는 외부의 침략으로부터 마을을 지킬 수 있는 부메랑 무기를 개발하는 공학자다. 길동이는 부메랑 제작을 위한 고급 나무 재료를 구했다. 이 나무 재료는 NxM크기의 직사각형 형태이며 나무 재료의 부위마다 그 강도가 조금씩 다르다.예를 들어 나무 재료의 크기가 2x3일 때는 다음과 같이 총 6칸으로 구성된다.길동이는 이처럼 넓은 사각형 형태의 나무 재료를 잘라서 여러 개의 부메랑을 만들고자 한다. 그리고 부메랑은 항상 3칸을 차지하는 ‘ㄱ’모양으로 만들어야 한다. 따라서 부메랑의 가능한 모양은 다음과 같이 총 4가지다. 이때 부메랑의 중심이 되는 칸은 강도의 영향을 2배로 받는다. 위 그림에서 노란색으로 칠한 부분..

https://www.acmicpc.net/problem/1352문제 : 골드 1Ideal String은 첫 문자의 인덱스를 1이라고 했을 때, 문자열에서 각각의 문자에 대해 그 문자가 가장 먼저 나타난 것의 인덱스만큼 그 문자가 나타나는 문자열이다.예를 들어, BAOOOA는 Ideal String이다. 그 이유는 B는 1번 등장하고, A는 2번, O는 3번 등장하기 때문이다.문자열의 길이 N이 주어졌을 때, 길이가 N인 가장 빠른 Ideal String을 출력하는 프로그램을 작성하시오. 만약 그런 문자열이 없을 때는 -1을 출력한다.입력첫째 줄에 N이 주어진다. N은 100보다 작거나 같은 자연수이다.출력첫째 줄에 정답을 출력한다. 풀이과정처음 문제를 보고 아이디어가 생각나지 않아서 손으로 종이에 n=..

https://www.acmicpc.net/problem/16238문제 : 골드 1독수리는 양을 먹으면서 살고 있다. 양이 사는 곳은 크기가 1×N인 직사각형으로 나타낼 수 있고, 1×1 크기의 칸으로 나누어져 있다. 칸은 왼쪽에서부터 1번, 2번, ..., N번으로 번호가 매겨져 있다. i번 칸에 사는 양의 수는 Ai마리이다.독수리는 매일 아침 양을 먹으러 간다. 1번 칸의 왼쪽이나 N번 칸의 오른쪽에서 날기 시작해 먹으려고 하는 양이 있는 칸까지 날아간다. 독수리는 칸을 벗어나서 날 수 없다. 먹으려고 하는 양이 있는 곳이 x번이라면, x번까지 날아간 다음, x번 칸에 있는 양을 모두 먹는다. 독수리는 하루에 한 칸에 있는 양만 먹을 수 있다.양은 독수리를 매우 무서워하기 때문에, 독수리가 나는 모습..

https://www.acmicpc.net/problem/11952문제 : 골드 2JOI국은 N개의 도시와 M개의 도로로 이루어져 있다. 모든 도시는 도로로 연결되어 있으며, 각 도로를 통하지 않고는 다른 도시로 갈 수 없다.이번에 K개의 도시는 좀비에 의해서 점령당했다. ㅠㅠ따라서 경곽이는 벙커가 있는 가장 안전한 도시로 피난을 가기로 했다. 경곽이는 현재 1번 도시에 살고 있으며, 벙커가 있는 가장 안전한 피난처는 N번 도시이다. 1번 도시와 N번 도시는 아직 좀비에게 점령당하지 않았다.경곽이는 각 도시를 이동할 때마다 1박을 해야하고, 1박을 할 때 숙박비를 지불해야 한다. 만약 그 도시가 좀비에게 점령당했다면 숙박이 불가능하다.좀비에게 점령당한 도시로 부터 S번 이하의 이동으로 이동할 수 있는 모..

https://www.acmicpc.net/problem/1941문제 : 골드 3총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.강한 결속력을 위해, 7명의 자리는..

https://www.acmicpc.net/problem/8980문제 : 골드 1아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다. 각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 ..

https://www.acmicpc.net/problem/4991문제 : 골드 1오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수..