31434번: 당근 클릭 게임 에릭은 방학 동안 너무 심심한 나머지, 당근 클릭 게임이라는 게임을 직접 만들어서 플레이하기로 했다. 이 게임에서 초기에 에릭은 당근을 $0$개 가지고 있고, $s$가 $1$인 상태로 게임을 시작한 www.acmicpc.net 2차원 DP 제목 당근 클릭 게임 조건 시간 제한 : 2 초 메모리 제한 : 1024 MB 문제 에릭은 방학 동안 너무 심심한 나머지, 당근 클릭 게임이라는 게임을 직접 만들어서 플레이하기로 했다. 이 게임에서 초기에 에릭은 당근을 0개 가지고 있고, s가 1인 상태로 게임을 시작한다. 그 후, 매초 다음 두 가지의 행동 중 하나를 할 수 있다. 1. 마우스를 클릭하고 당근을 s개 얻는다. 2. 정수 i(1 ≤ i ≤ N)를 고르고, 당근 Ai개를 지..
30985번: 직장인 파댕이의 사회생활 첫째 줄에 방의 수 $N (2 \leq N \leq 100,000)$과 복도의 수 $M (1 \leq M \leq 300,000)$, 건물의 층수 $K (2 \leq K \leq 200,000)$가 공백으로 구분되어 주어진다. 다음 줄부터 $M$개의 줄에 걸쳐 세 정수 $u, v, c$가 공 www.acmicpc.net 층을 생각하지 않는다 1부터 X번방까지 최소 거리 X번방부터 N번방까지 최소 거리 다익스트라 제목 직장인 파댕이의 사회생활 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 파댕이는 중견기업 회사에서 직장인으로 일하고 있다. 사장님이 직장인 파댕이를 무척 아끼기 때문에, 파댕이는 사장실에 찾아가 사장님께 인사를 하려고 한다. 직장인 파댕..
최소 공정 수를 이분탐색 제목 공정 컨설턴트 호석 조건 시간 제한 : 1 초 메모리 제한 : 512 MB 문제 거듭된 창업 성공을 이룬 류진국 사장은 이번에는 맞춤형 선물을 제작해주는 공장을 만들기로 했다. 현재 들어온 맞춤형 선물 주문은 총 N개이며, 각 맞춤형 선물마다 제작에 필요한 시간이 정해져있다. 주문의 번호는 1번부터 N번까지 매겨져 있으며, 다음과 같은 규칙에 맞게 공정이 이뤄진다. 1. 공정 라인이 총 K개가 있다면 1번부터 K번까지의 번호가 존재한다. 2. 공정 라인의 사용 시간은 배정된 맞춤형 선물들의 제작 시간의 총합이다. 3. i번 선물은 1번 부터 i1번 선물들이 배정된 이후에 사용 시간이 가장 적은 공정 라인 중 하나에 배정된다. 모든 맞춤형 선물의 제작이 완료될 때까지 최대 X..
자바를 사용하면서 조건별로 숫자로 표현된 값을 파싱해서 출력해야하는 경우가 있는데 이를 정리하고자 한다. 1. System.out.printf() 출력과 함께 바로 소수점을 파싱할 때 사용하면 좋다고 생각한다. System.out.printf("%.6f", value); 2. String.format() System.out.println()과 함께 사용해야 하는 경우에는 System.out.printf() 대신 String.format() 함께 사용하는 것이 좋다고 생각한다. 소수점으로 파싱된 문자열이 리턴된다. String.formant("%.6f", value); 3. Math.round() Math.round()는 소수점 첫째자리에서 반올림하는 것을 이용한 것이다. Math.round(value *..
30459번: 현수막 걸기 첫째 줄에 말뚝의 개수 $N$, 깃대의 개수 $M$, 쿠가 살 수 있는 최대 현수막 넓이를 나타내는 정수 $R$이 공백으로 구분되어 주어진다. $\left( 2\leq N\leq 2\, 000;\ 1\leq M\leq 40\, 000;\ 1\leq R\leq 10^{9} \right)$ www.acmicpc.net 1. 말뚝 두개 선택 (N * N) 2. R보다 작으면서 최대인 깃대를 이분탐색으로 선택 제목 현수막 걸기 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 쿠는 KUPC를 홍보하기 위해 삼각형 모양의 거대한 현수막을 제작하고자 한다. 현수막을 걸 수 있는 지면에는 N개의 말뚝이 한 줄로 박혀 있다. 쿠는 말뚝과 미리 준비해 둔 M개의 깃대 중 하나를 이..
24395번: 명진이의 신년계획 첫째 줄에 N (1 ≤ N ≤ 100,000), M (1 ≤ M ≤ 100)이 공백을 두고 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 M개의 질병에 처방할 빨강, 파랑 알약의 수 Ri , Bi (0 ≤ Ri , Bi ≤ 50, Ri + Bi ≥ 1)와 위험도 www.acmicpc.net DP + 배낭 제목 명진이의 신년계획 조건 시간 제한 : 1 초 메모리 제한 : 512 MB 문제 카오스 동아리 사람들은 모두 코딩에 미쳐있기 때문에 주기적으로 약을 처방받는다. 동아리의 회장 명진이는 새해를 맞아 이들 모두를 치료하고자 한다. 그들이 걸린 질병은 총 M종류이며 각 질병은 0 이상, 100 이하의 위험도를 지닌다. 회원들은 걸린 질병에 따라 특정 개수의 빨강, 파랑 알약을 처..
20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 4가지 변수를 모두 사용하기에는 시간초과 우려 600^4 하나의 눈사람을 고정시키고 다른 최적의 눈 사람을 구하기 제목 같이 눈사람 만들래? 조건 시간 제한 : 2 초 메모리 제한 : 1024 MB 문제 언니! 똑...똑똑...똑똑! 같이 눈사람 만들래~? ♪ 언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 ..
27314번: 러키☆한별 첫 번째 줄에 미로의 높이 $N$과 너비 $M$이 공백으로 구분되어 주어진다. ($1 \leq N, M$, $N \times M \leq 100\, 000$) 다음 $N$개의 줄에 미로의 정보가 길이 $M$인 문자열로 주어진다. 문자열에서 H는 한별이 www.acmicpc.net 선물이 먼저 도착해서 기다린다면? 제목 러키☆한별 조건 시간 제한 : 2 초 메모리 제한 : 1024 MB 문제 한별이는 운이 매우 좋다! 한별이는 벽, 다른 사람들, 그리고 여러 개의 출구가 있는 미로를 탈출하고자 한다. 미로 내에서 한별이와 다른 사람들은 매 순간 상하좌우 중 한 방향으로 한 칸 이동할 수 있다. 또, 한별이가 아닌 다른 사람들은 멈춰있을 수도 있다. 벽이 있는 칸으로 이동하거나 미로..
DP[N] = 길이 N을 만들기위한 최대용량 제목 수도배관공사 조건 시간 제한 : 2 초 메모리 제한 : 128 MB 문제 아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 했다. 근처의 인간 마을에서 P개(1 ≤ P ≤ 350)의 파이프를 매입했는데, 각각은 길이 Li와 용량 Ci로 나타낼 수 있다. (Li와 Ci는 모두 2^23보다 작거나 같은 양의 정수이다) 파이프들은 일렬로 이어서 수도관 하나로 만들 수 있으며, 이때 수도관의 용량은 그것을 이루는 파이프들의 용량 중 최솟값이 되고, 수도관의 길이는 파이프들 길이의 총합이다. 수도관을 한 개 만들어 ..
31413번: 입대 드디어 병역의 의무를 질 나이가 된 용진이는 선진병영을 선도하는 대한민국 공군병 모집에 지원하고자 한다. 대한민국 공군 모집병으로 합격하기 위해선 가산점이 필요한데, 최근 높아진 공군 www.acmicpc.net 2차원 DP 헌혈 횟수와 일수 제목 입대 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 드디어 병역의 의무를 질 나이가 된 용진이는 선진병영을 선도하는 대한민국 공군병 모집에 지원하고자 한다. 대한민국 공군 모집병으로 합격하기 위해선 가산점이 필요한데, 최근 높아진 공군의 인기 탓에 봉사활동 혹은 헌혈을 통해 M점 이상의 가산점을 모아야 한다. 현재 공군 지원일까지는 N일이 남았으며, 그중 i일에는 si점의 가산점을 얻을 수 있는 봉사활동에 참여할 수 있다. ..
20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 좌표를 1차원으로 압축하여 사용 백트래킹 제목 진우의 민트초코우유 조건 시간 제한 : 1 초 메모리 제한 : 512 MB 문제 진우는 민트초코우유를 좋아하는 민초단이다. 힘든 일이 있더라도 민트초코우유 하나를 마시면 기운이 펄펄 솟는다고 한다! 민트초코우유를 너무 좋아하는 나머지 진우는 매일 아침 특정 지역들에서 민트초코우유가 배달된다는 N × N 크기의 2차원 민초마을로 이사를 하였다. 진우는 아침에 눈을 뜨면 집에서 민초마을의 지도를 들고 ..
23563번: 벽 타기 출발하자마자 오른쪽으로 한 칸 이동하고, 위로 한 칸 벽을 타고 이동하면 총 1의 시간이 소요된다. www.acmicpc.net 벽 타기를 하려면 내가 현재 있는 곳이 벽과 인접해야하고 내가 가야할 곳이 벽에 인접해야한다 최단경로를 구해야할 때 경로 중간에 최적의 경로가 생길 수 있다면 다익스트라로 구현해야한다 제목 벽 타기 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 루시우는 높이가 H이고 너비가 W인 맵의 시작점에서 끝점까지 이동하려고 한다. 맵은 H개의 행과 W개의 열로 이루어진 격자판 모양이다. 각 칸은 벽 또는 빈칸이다. 루시우는 상, 하, 좌, 우 방향 인접한 칸으로 한 칸씩 이동할 수 있다. 벽으로는 이동할 수 없다. 루시우가 한 칸을 이동하는 데에는 ..
