문제 이해 단계 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개..

문제 이해 단계 https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 정점과 간선 정보가 주어진다. 각 간선은 단방향으로 주어지고, 간선에는 시간이라는 가중치가 존재한다. 여기서 선택해야 하는 것은 왕복 시간(목적지로 갔다가 다시 돌아오는데 드는 시간)이 가장 많이 드는 사람의 시간을 최소화하는 도시를 선택하는 것이다. 도시의 개수 N과 간선의 개수 M, 그리고 사람 수 K와 각 사람이 사는 도시 정보가 주어진다. 왕복 시간이 가장 많이 드는 사람의 시간을 최소화하는 도시를 출력하고, 만약 여러 개..

문제 이해 단계 https://www.acmicpc.net/problem/13019 13019번: A를 B로 첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다. www.acmicpc.net 대문자 알파벳으로 이루어진 문자열 A와 B가 입력으로 들어온다. 문자열 A를 B로 바꾸는 것이 목표. 할 수 있는 연산은 알파벳 하나를 골라 가장 앞으로 보내는 것이다. 이때 최소 몇 번 만에 만들 수 있는지 구하는 문제 문제 접근 단계 일단 입력으로 들어오는 문자열의 길이가 50이 넘지 않는다. 따라서 시간초과는 크게 신경 쓰지 않아도 될 것 같다. 연산에서 중간에 있는 문자를 골라도 상관이 없다. 하지만 무조건 가장 앞으로 보내..