그건 장난감이 아니라 돌이야

https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 접근 처음에는 LCS가 무조건 이어진 문자열 이어야 한다고 생각해서 이어진 문자열에 대한 코드를 작성했다. 악랄하게도 주어진 예제도 그렇게 이해하고 풀 수 있는 예제였다 ㅠ 예제 입력 abc abc ac 예제 출력 2 a, b가 떨어져있더라도 그냥 띄어서 개수를 셀 수 있다는 것이다.. 위와 같은 반례가 있기 때문에 다르게 다 풀고서 처음부터 다시 접근했다. 해결 기본적으로 DP로 풀어야한다는 감이 온다. (a..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 미완성된 스도쿠 판이 입력으로 주어질 때, 스도쿠판을 완성해서 출력하는 문제이다. 이 문제는 일단 N-Queen과 굉장히 유사하다. N-Queen문제를 생각해보면 보드에서 모든 자리를 살펴보는데 각 자리에 대해서 queen을 놓을 수 있는지 없는지 판단한 뒤, 놓을 수 있는 경우에는 놓고 지나거나 안 놓고 지나가고, 놓을 수 없는 경우에는 안놓고 지나간다. 이러한 백트래킹은 다음과 같은 논리..

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 정수 N이 주어질 때, N번째 감소하는 수를 출력하는 문제이다. 321, 9741, 987654321 등은 감소하는 수의 예시다. 일단 N번째 수를 찾으려면 그 전의 수부터 찾아가면서 백트래킹으로 N번째 수에 도달하는 방법을 사용해야 함을 알 수 있다. 백트래킹을 어떻게 수행할지 결정하기 위해서는 우선, 어떤 규칙으로 수를 카운팅 해야하는지 수열의 규칙을 분석해봐야 한다. 이 문제에..

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net "Dance Dance Revolution" 일명 DDR을 플레이할 때, 왼발과 오른발의 위치에 따라 다음 버튼을 누르는데 소비하는 에너지가 다르다면 눌러야하는 버튼이 순서대로 주어졌을 때, 가장 적은 에너지로 버튼을 누를 수 있는 에너지를 구하는 문제이다. 일단 비슷한 문제가 하나 생각나는데 [2618번]경찰차 문제가 생각난다. 하지만 이 문제가 더 단순화된 버..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 하얀 방(1)과 검은 방(0)으로 구성된 1*1 크기의 방들이 n*n크기의 맵을 이루고 있다. 이때, (1, 1)에서 (n, n)까지 가고 싶은데 검은 방은 지나갈 수 없으므로 하얀 방으로 색을 바꾸고 지나가야 한다. 이때 검은 방의 색을 최소한의 횟수로 바꾸고 (n, n)에 도달하려면 몇 번 바꿀 수 있는지 알아보는 문제이다. 얼핏 보면 벽 부수고 지나가기 시리즈를 생각할 수 있는 문제이다. 하..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 공기구멍이 송송 뚫려있는 치즈가 있을 때, 바깥공기와 닿은 치즈 부분이 한 층씩 녹아내리는 상황을 시뮬레이션하는 문제이다. 일단 2차원 맵에서 탐색을 해야한다는 것을 봤을 때 직관적으로 BFS가 생각난다. 아니나 다를까 이 문제는 BFS를 사용해서 한 층씩 치즈의 겉을 녹여라! 라는 문제이다. 문제에서는 친절하게 맵의 가장자리는 무조건 공기로 채워져 있다는 제약조건을 준다. 만약 가장자리까지 치즈가 있을 ..

https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아 www.acmicpc.net W x H 크기의 맵이 있는데 맵의 (0, 0)에서 (W-1, H-1)까지 탈출할 수 있는지 없는지, 혹은 무한 루프가 존재할 수 있는지 알아내는 문제이다. 맵에는 잔디, 묘비, 귀신 구멍이 있다. 세 요소를 정리해서 문제를 단순화해서 이해해보자. - 잔디 : 빈 칸 (지나갈 수 있는 칸), 이 칸으로 올 때, 간선의 가중치는 1이다. - 묘비 : 벽 (지나갈 수 없는 칸) - 귀신 구멍 : 상하좌우론..

https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 1번부터 N번까지 번호가 붙은 노드가 있고, 양의 가중치를 가진 무방향 간선을 하나씩 그래프에 붙일 때, s노드와 t노드가 최초로 연결되는 순간이 있다. 간선들을 붙이는 순서를 마음대로 조정할 때, 이 s노드와 t노드가 최초로 연결되는 순간에 s노드와 t노드를 잇는 간선들의 가중치의 합이 최소가 되는 순간의 가중치의 합을 구하는 문제이다. 이 문제는 복잡하게 보일 수 있지만 생각해 보면 문제..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net N개의 물건이 주어지고 그 물건들에 대한 대소관계가 M개 주어질 때 각 물건들끼리 대소 관계를 파악할 수 있는지 없는지를 파악하는 문제이다. 이 문제에서 주목해야 할 포인트는 두가지 정도이다. 1. 저울의 대소관계는 방향성 그래프의 간선으로 생각할 수 있다. 예를 들어 A B, B -> C로의 단방향 간선 두 개로 생각할 수 있다. 2. ..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 오랜만에 눈물의 AC를 받은 문제이다. LCS의 길이를 구하는 것 까지는 설명을 듣고 이해할 수 있었다. 하지만 실제 LCS를 구하는 방법에서 막혀서 시간이 걸렸다. 다음과 같은 순서로 LCS를 구하는 문제에 접근했다. 1. string2차원 배열을 만들고, DP 배열을 채울 때 string 배열도 DP가 채워짐에 따라서 똑같이 채우는 방법. 하지만..