문제 이해 단계 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net N명이 학생이 있고 그 학생들 사이에 M개의 친구 관계가 존재한다. 그리고 각각의 학생마다 친구비가 존재하는데, 친구 관계인 친구였다면 그중 하나에게만 지불하면 된다. 해당 조건으로 K원을 가지고 있을 때, N명 학생과 모두 친구를 맺을 수 있는 최소 비용을 구하시오. 만약 구할 수 없으면 "Oh no"를 출력한다..

문제 이해 단계 https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net n개의 정점과 m개의 간선이 존재한다. 그리고 간선 사이에는 가중치가 존재한다. 모든 정점에서 다른 정점으로의 경로표를 만들어야 한다. 한 정점에서 다른 정점으로 최단경로로 움직일 때, 거쳐야 하는 다른 정점을 경로표에 적어 넣는다. 그리고 경로표 전체를 출력하는 것이 해당 문제이다. 문제 접근 단계 로직 유추 문제를 보면 바로 정점과 간선이 있는 그래프를 준다. 이 점을 보니 바로 그래프..

문제 이해 단계 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net MxN짜리 맵에 입력으로 출발 좌표와 목적 좌표가 주어진다. 출발지에서 로봇이 출발하는데 로봇이 할 수 있는 행동은 아래의 2가지이다. 명령 1. Go k : k는 1,2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸만큼 움직인다. 명령 2. Turn dir : dir은 left 또는 right이며, 각각 왼쪽 또는 오른쪽으로 90도 회전한다. 로봇을 목적지에 도착시키고, 원하는 방향..

문제 이해 단계 https://www.acmicpc.net/problem/16432 호랑이에게 N일 동안 떡을 줘야 한다. 떡을 줄 때 이틀 연속해서 같은 번호의 떡을 주어선 안된다. 떡의 종류는 1~9번까지 총 9개가 존재한다. 입력으로 N일이 들어오고, 그다음 줄부터 i번째 날의 가져갈 떡의 수 m과 떡의 종류가 주어진다. 호랑이에게 떡을 줄 수 있는 경우엔 여러 가지 경우의 수 중 하나를 출력하고, 그렇지 않은 경우엔 -1을 출력한다. 문제 접근 단계 제한사항부터 살펴보면, N(일)의 최대는 1,000이다. 떡의 종류는 최대 9개까지 가능하다. 아이디어 처음에는 당연히 연속되는 경우를 제외하고, 모든 종류를 하나씩 살펴보는 백트래킹 방식을 사용하려고 했는데 이 방식은 8^1,000이 되기 때문에 시..

문제 이해 단계 https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 일렬로 나열되어 있는 정수가 1 ~ N까지 존재한다. 이 숫자들을 얻기 위해서는 양끝부터 얻어야 한다. 숫자를 얻었을 때 이익은 다음과 같다. 이익 = 숫자*(고른 순서) 해당 조건과 같을 때 얻을 수 있는 가장 최대의 이익을 구하는 문제 문제 접근 단계 벼의 개수는 최대 2,000개까지, 그리고 정수는 최대 1,000까지 가능하다. 일단 정수를 양쪽 끝에서부터 얻을 수 있기 때문에 왼쪽과 오른쪽을 분리해서 생각하긴..

문제 이해 단계 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net N개의 지점과 그 지점 사이에는 M개의 도로와 W개의 웜홀이 존재한다. 여기서 도로는 양방향이고 웜홀은 단방향이다. 도로와 웜홀의 정보는 공통적으로 (시작 지점, 도착 지점, 가는 시간)으로 들어온다. 웜홀은 시작했을 때보다 도착했을 때 시간이 거꾸로 가게 된다. 한 지점에서 출발하여 다시 출발했던 지점을 돌아올 때, 출발했을 때보다 시간이 돌아가있는 것이 가능한가?를..

문제 이해 단계 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net NxN 크기의 맵에 대나무가 각 칸에 존재한다. 대나무는 정수값이다. 판다가 이걸 먹는데, 먹고 난 이후에는 상하좌우로 움직인다. 판다는 움직일 때, 먹은 그 칸의 대나무보다 많은 칸으로밖에 이동하지 못한다. 맨 처음 판다를 놓을 수 있는 칸을 정할 수 있을 때, 판다가 최대한 많이 움직일 수 있는 칸의 수를 구하는 문제 문제 접근 단계 일단 맵의 크기는 최대 500x5..

문제 이해 단계 https://www.acmicpc.net/problem/20924 노드의 개수 N과 루트 번호 R이 들어온다. 그리고 N-1개의 노드 정보가 주어지는데, (a, b, c) -> a번 노드와 b번 노드가 연결되어 있는데 길이는 c이다. 그리고 기가 노드라는 것이 존재하는데, 이는 루트노드에서 시작했을 때 최초로 자식 노드가 2개 이상인 노드이다. 또는, 리프 노드가 단 1개인 경우엔 리프 노드인 동시에 기가 노드이다. 그리고 루트노드인 동시에 기가노드 또한 가능하다. 루트 노드 ~ 기가노드까지를 기둥이라고 하고 기가노드 ~ 임의의 루프노드를 가지라고 할 때, 기둥 길이의 합을 구하고, 가지 중 가장 길이가 긴 것을 출력해라. 문제 접근 단계 일단 조건부터 보면 노드는 최대 200,000개..