www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net (저도 이 문제를 보기 전까지 녹색 옷 입은 애가 젤다인 줄 알았습니다.) n x n 동굴에 주인공이 0,0 지점에 있다면 n-1, n-1 까지 도달할 때 최소한의 검정 루피를 밟고 가도록 하는 문제입니다. 다익스트라 알고리즘을 이용해 시작지점이 0,0으로 정해져 있으므로 모든 지점을 탐색하면서 최소 경로로 만들어주면 됩니다. 그리고 마지막으로 n-1, n-1 지점의 최소 경로 값을 구해주면 ..
www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 터널 내의 차선 변경이 불가능할 때 추월 차량이 얼마나 되는지 묻는 문제입니다. (하지만 실제로는 큰 터널의 경우 추월가능한 터널도 있다.) 처음에는 dp로 생각하여 들어갈 때 내 차량 앞에 몇 대의 차량이 있는지를 계산하여 풀려했지만, 예제 몇 개를 떠올려보니 2번이 1번을 추월하고 1번이 2번을 다시 추월하고 그러면 계산이 꼬이는 경우가 있어서 다른 방법으로 풀었습니다. C++에서 map 컨..
www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 예전에 푼 문제인데 재채점 되면서 틀렸다하여 다시 풀었다. 바이토닉 수열이란 수열이 S1 S_k+1 > ... > Sn 을 만족하는 k가 존재하는 수열을 말한다. 수열이 주어졌을 때, 부분 수열 중 가장 긴 바이토닉 수열의 길이를 구하면 된다. 수열의 길이가 1000개이므로 O(N^2) 정도로 풀어도 충분한 시간이다. 수열의 n번째 원소를 arr[n] 이라 하고, dp[n]을 arr[n]을 부분 수열..
www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 처음에는 하드코딩으로 길을 열심히 만들어 하려했는데 너무 햇갈려서 때려치웠다. 두 번째로 경로 별로 indexing 하여 파란칸인지 아닌지를 결정하려 했지만, 중간에 도착지점이 끼어있다고 생각하니 말이 도착 지점 이동 후에 엉뚱한 곳으로 가는 경우가 발생하여 접었다. 그래서 다른 분들의 풀이를 참고하였다. map의 칸의 index와 점수를 구분하여 게임을 한다. (이렇게 안 하고 map 배열 하나로 처리하려 해서 너무 햇갈렸다.) 파란 칸인 경우는 turn 배열을 이용해 해당 index의 turn값이 0이 아니면 파란 경로란 의미이다. ..
www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 간단한 위상정렬 문제였습니다. 기본적으로 숫자가 작을 수록 쉬운 문제이고, 먼저 풀어야하는 우선순위가 정해져있을 때 문제를 푸는 순서를 구하는 문제입니다. 1번을 먼저 풀고 3번을 풀고, 1번을 먼저 풀고 4번을 풀어야한다고 하면 (1->3, 1->4) 문제 푸는 순서는 1, 3, 4도 되고 1, 4, 3도 되지만, 3 < 4이므로 1, 3, 4가 정답이 되는 그런 문제입니다. 먼..