문제 링크https://www.acmicpc.net/problem/10021 문제Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 Each field i is described by a distinct point (xi, yi) in the 2D plane, with 0 (xi - xj)^2 + (yi - yj)^2FJ would like to build a minimum-cost system of pipes so that all of his fields are linked together -- so that water in any field can follow..

문제 링크https://www.acmicpc.net/problem/11663  문제일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다. 출력입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다. 예제 입력 15 51 3 10 20 301 1020 603 302 154..

문제 링크https://www.acmicpc.net/problem/11568 문제민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 정해진 순서대로 보여줄 것이다. 준민이는 앞의 카드부터 임의의 개수만큼 골라서 민균이에게 제시하게 되는데, 제시한 카드의 수열이 순증가가 아니면 민균이에게 바보라고 놀림받게 된다. 예를 들어 민균이가 보여준 카드가 {4, 9, 10, 9} 일 때 준민이가 {4, 9}를 골랐다면 놀림을 받지 않겠지만, {4, 10, 9}이나 {9, 9}를 제시하면 놀림받게 될 것이다.생각보다 바보가 아닌 준민이는 한번도 민균이에게 놀림을 받지 않았다. 이에 분..

문제 링크https://www.acmicpc.net/problem/25682 문제지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다.체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로..

문제 링크https://www.acmicpc.net/problem/14430 문제인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. WOOK은 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있으며, 그 외의 방향으로 움직이는 것은 불가능하다. WOOK은 자신이 위치한 (x, y)에 자원이 있는 경우에만 해당 자원을 채취할 수 있다. WOOK이 탐사할 영역에 대한 정보가 주어질 때, WOOK이 탐색할 수 있는 자원의 최대 숫자를 구해라! 입력첫째 줄에 WOOK이 탐사할 영역의 세로길이 N(1≤N≤300)과 가로길이 M(1≤M≤300)이 주어진다..

문제 링크https://www.acmicpc.net/problem/31869 문제24학번 신입생 정민이는 밥을 사준다는 선배들의 약속을 모두 메모장에 기록해 둔다. 메모장의 각 줄에는 선배 이름 𝑆, 약속 주차 𝑊, 요일 𝐷, 밥 약속에 드는 비용 𝑃가 기록돼 있다. 선배 이름은 문자열, 나머지는 정수로 기록한다. 또, 한 선배는 두 번 이상 밥을 사주지 않으며 모든 선배의 이름은 다르다.정민이는 컴퓨터학부답게 요일을 0과 6 사이의 정수로 기록한다. 예를 들어 월요일은 0이고 목요일은 3이다.정민이의 착한 선배들은 밥을 사줄 수 있는 충분한 돈이 있다면 귀여운 후배와의 밥 약속을 무를 수 없다. 정민이의 기록과 선배들이 지닌 돈을 보고 정민이가 최대 며칠 연속으로 밥을 얻어먹을 수 있는지 구해보..

문제 링크https://www.acmicpc.net/problem/30971 문제진주 나들이를 온 보선이는 배가 너무 고파 육회비빔밥을 먹기 위해 진주 대안동에 갔다. 그런데 이게 웬 떡? 육회비빔밥 시식 행사가 진행 중이었다. 대식가이자 미식가인 보선이는 육회비빔밥을 감칠맛이 최대한 나게끔 전부 먹으려고 한다. 하지만 전부 먹으려고 하니 아무리 뻔뻔한 보선이라도 시식대 직원의 눈치가 조금 보이기 시작했다. 그래서 각 시식대의 정보를 파악해서 전략적으로 먹기로 했다.육회비빔밥 시식대는 총 𝑁개가 있다. 각 시식대에는 육회비빔밥 한 그릇과 직원 1명이 있으며, 육회비빔밥의 단맛과 짠맛 그리고 그곳에 있는 직원이 눈치 주는 정도는 수치로 나타낼 수 있다. 보선이는 육회비빔밥이 남아 있는 시식대 중 하나를 ..

문제 링크https://www.acmicpc.net/problem/31849 문제왕복 4시간 통학에 지친 현성이는 자취방을 구하려고 한다.현성이가 방을 고르는 기준은 월세와 편의점까지의 거리뿐이다. 가장 마음에 드는 방을 구하기 위해 현성이는 지도 위의 모든 방에 편세권 점수를 매겨 그 중 편세권 점수가 가장 낮은 집을 고르려고 한다. 편세권 점수의 계산 방식은 다음과 같다. 편세권 점수 = (방에서 가장 가까운 편의점까지의 거리 × 월세) 현성이가 보고 있는 지도는 𝑁×𝑀 크기의 격자로 이루어져 있다. 지도의 𝑥행 𝑦열에 있는 칸의 위치를 (𝑥, 𝑦)로 나타내자. 방의 위치가 (𝑎, 𝑏), 편의점의 위치가 (𝑐, 𝑑)일 때 방에서 편의점까지의 거리는 |𝑎 − 𝑐| + |𝑏 − ?..

문제 링크https://www.acmicpc.net/problem/16208 문제현우는 무슨 이유에선지 길이 a1, ..., an의, 총 n개의 쇠막대가 필요해졌다. 하지만 그가 가진 것은 길이 a1+...+an의 하나의 쇠막대뿐이었다. 현우는 이 막대를 직접 잘라서 원래 필요하던 n개의 쇠막대를 만들 것이다. 길이 x+y인 막대를 길이 x, y인 두 개의 막대로 자를 때에는 만들려 하는 두 막대의 길이의 곱인 xy의 비용이 든다. 현우는 최소의 비용으로 이 쇠막대를 잘라서 a1, ..., an의 n개의 쇠막대를 얻고 싶다.그런데 현우는 이 비용이 얼마나 들지 잘 모르겠다. 그래서 여러분이 막대를 자르는 최소 비용을 계산하는 프로그램을 작성해주면 코드잼 경시대회 점수를 30점 올려주겠다고 제안했다. 어떤..

문제 링크https://www.acmicpc.net/problem/20364 문제이진 트리 모양의 땅으로 이루어진 꽉꽉마을에는 오리들이 살고 있다. 땅 번호는 다음과 같이 매겨진다.루트 땅의 번호는 1이다.어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 × K, 오른쪽 자식 땅의 번호는 2 × K + 1이다.어느날 오리들끼리 부동산 다툼이 일어나서 꽉꽉마을 촌장 경완이가 해결책을 가져왔고, 그 내용은 다음과 같다.오리들을 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 위치해 있다.오리들이 서있는 순서대로 원하는 땅을 가지도록 한다. 만약, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 막대한 세금을 내야 하는 이유로 해당 땅을 지나가지 못해 그 오리는 땅을 가지지 못한..

문제 링크https://www.acmicpc.net/problem/31946 문제지훈이는 등굣길에서 보도블록을 지날 때 같은 색의 보도블록만을 밟으면서 이동한다. 왜냐하면 다른 색의 보도블록을 밟으면 사망하기 때문이다.등굣길은 𝑁 × 𝑀 크기의 행렬로 표현할 수 있으며 행렬의 각 원소는 하나의 보도블록으로 이루어져 있다. 지훈이는 1행 1열에서 출발해 𝑁행 𝑀열에 도착해야 한다.빨간색 또는 회색으로 이루어진 등굣길을 이동하면서 지훈이는 현재 밟고 있는 보도블록과 같은 색의 보도블록만을 밟고 이동해야 한다. 또한 지훈이의 점프력이 𝑋이기 때문에 맨해튼 거리가 𝑋 이하인 보도블록으로만 이동할 수 있다. 지훈이가 무사히 등교를 마칠 수 있는지 알려주자. 입력첫째 줄에 등굣길의 행의 개수 𝑁이 주어..

문제 링크https://www.acmicpc.net/problem/31804 문제자료구조 시험에서 우찬이는 a점을 받았고, 상훈이는 우찬이보다 높은 b점을 받았다. 우찬이는 상훈이보다 점수가 낮아서 화가 났지만, 공부를 하나도 하지 않아서 상훈이보다 시험을 잘 볼 수는 없다는 것을 알고 있었다. 하지만 우찬이는 최소한 동점을 받고 싶었기 때문에, 자신의 수를 바꾸는 마법을 배워서 다음 3가지 마법을 사용할 수 있게 되었다. 물 주기: 수에 물을 주면 수가 1 커진다.밥 주기: 수에 밥을 주면 수가 2배가 된다.chance!: 수에 chance!를 외치면 수가 10배가 된다.하지만 chance!를 외치면 목이 너무 아프기 때문에 우찬이는 chance! 마법을 최대 한 번만 사용할 수 있다. 그리고 마법을 ..

문제 링크 https://www.acmicpc.net/problem/14615 14615번: Defend the CTP!!! 첫 번째 줄에 N(3≤N≤100,000)과 M(1≤M≤1,000,000)이 주어진다. N은 CTP에 존재하는 도시의 개수를 의미하고 M은 CTP에 존재하는 튜브의 개수를 의미한다. 다음 M개의 줄에 걸쳐 X, Y(1≤X, Y≤N)가 주어지 www.acmicpc.net 문제 지금으로부터 527년이 지난 서기 2544년, 항성 간 이동이 가능해진 인류는 태양계가 아닌 새로운 보금자리를 찾아 기술의 집약체인 CTP(Cho Technology Planet, 초 기술 행성)를 건설한다. 인공지능이 관리하는 CTP 안에서는 자연재해도 전쟁도 없었으며 많은 사람이 행복을 누리며 살아나갔다. C..

문제 링크 https://www.acmicpc.net/problem/5547 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 문제 부유한 집안의 상속자 상근이네 집은 그림과 같이 1미터의 정육각형이 붙어있는 상태이다. 크리스마스가 다가오기 때문에, 여자친구에게 잘 보이기 위해 상근이는 건물의 벽면을 조명으로 장식하려고 한다. 외부에 보이지 않는 부분에 조명을 장식하는 것은 낭비라고 생각했기 때문에, 밖에서 보이는 부분만 장식하려고 한다. 위의 그림은 상공에서 본 상근이네 집의 건..

문제 링크 https://www.acmicpc.net/problem/31476 31476번: :blob_twintail_thinking: 첫째 줄에는 양갈래 굴의 방 중 가장 깊은 곳의 깊이 $D(1 \le D \le 12)$와 파손된 길목의 수 $N(0 \le N \le 2^D-2)$, 각 블롭 세력이 기본적으로 탐색하는 시간인 $U(1 \le U \le 100)$와 양갈래 블롭들이 갈라 www.acmicpc.net 문제 블롭들은 늘 새로움을 추구해 왔다. 이번에도 블롭들은 새로운 느낌을 원하였고, 이에 블롭들은 매일매일 하늘에 기도하게 된다. 이 기도를 들은 토카는 블롭들에게 양갈래 머리를 하사하였으며, 블롭들은 대 양갈래 시대를 맞게 된다. 그러나, 일부 블롭들은 거기서 더 새로운 헤어 스타일을 추..