이 험난한 세상에서어어~

문제 설명 N개의 줄에 0부터 9이하의 숫자가 총 3개씩 주어진다. 이때 첫 번째 행에서부터 놀이를 시작하는데, 바로 아래 숫자 혹은 바로 아래와 연결된 숫자로 내려갈 수 있다. 이때 가능한 최댓값과 최솟값을 구하는 문제이다. https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 여기서 바로 아래의 숫자라는 건 숫자라는 개념의 순서가 아닌 물리적인 위치의 아래를 의미한다. 문제 풀이 문제집에서는 투 포인터 혹은 슬라이딩 윈도우로 분류가 되어 있지만, dp와 비슷한..

문제 설명 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제가 길다. 아무튼 간단하게 말하자면 하나의 땅에서 다른 땅으로 가는 최대 거리를 구하는 문제이다. 처음 보고는 플로이드 외샬 알고리즘이 생각났으나, 이를 위해서는 따로 그래프를 만들어 줘야 하니 일단 너비 우선 탐색으로 풀어줬다. 문제 풀이 모든 L에서부터 시작해서 갈 수 있는 L까지 너비 우선탐색을 해준 다음에 최대 거리를 찾아주면 된다. 사실 전통적인 너비 우선 탐색 문제 풀이에서 ..

문제 설명 파이프를 옮겨 (n, n) 칸 까지 갈 수 있는 경우의 수가 총 몇 가지인지를 묻는 문제이다. 이때, 초반의 파이프는 무조건 (1, 1)과 (1, 2)를 차지하고 있고 총 세 가지 방향으로 움직일 수 있다. 파이프가 움직일 수 있는 방향은 오른쪽, 아래, 오른쪽 대각선 아래인데 이때 파이프는 45도 방향으로만 회전시킬 수 있다. 그렇기에 오른쪽 방향 파이프는 오른쪽 혹은 오른쪽 대각선 아래로만, 아랫 방향 파이프는 아래 혹은 오른쪽 대각선 아래로만, 오른쪽 대각선 아래 방향 파이프는 전부다 가능하다. https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의..

문제 설명 trie 문제집으로 분류되어 있기는 하지만, 구현 문제다. 그리고 굳이 trie를 안 써도 풀린다... 아무튼 해당 문제에서 특이한 점은 주어진 행렬이 이어져 있다고 생각해야 한다는 점이다. 예를 들어서 (0,0)에서 한 칸 위로 올라가면 (-1,0)이 된다. 그렇다면 해당 좌표는 탐색하지 않는 것이 옳지만, 행렬이 이어져 있다고 생각해야 하니 (2,0)을 탐색해줘야 한다. 즉, 좌표가 0보다 작으면 n-1 혹은 m-1의 위치로 들어가고 n 혹은 m의 위치가 되면 0으로 들어가야 한다는 것이다. 그리고 대각선도 탐색해야 한다는 것을 잊어서는 안 된다. 그리고 출력 부분도 조심해야 한다. 문제에서는 신이 좋아하는 문자열은 중복될 수 있다고 했다. 그러므로 중복된 문자열 또한 해당 문자열의 결과 ..

문제 설명 방향성 없는 그래프가 주어질 때 1부터 n까지 v1과 v2를 지나서 가는 최단 경로를 구하는 문제이다. https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 풀이 첫 번째 접근 다익스트라로 풀어주면 되지만 v1과 v2를 지나가야 한다는 것이 문제이다. 여기서 갈 수 있는 경로는 1에서 v1, v2, n이거나 1에서 v2, v1, n이다. 간단하게 생각해주면 되는데, 일단 1부터 시작하는 다..