https://www.acmicpc.net/problem/1230 틀렸던 문제 다시 풀기 3일차.골드1을 보고 당황 했지만,,, 하루에 딱 한 시간만 투자한다는 생각으로 도전했다.4일정도 걸린 것 같은데, 문제를 고민하는 데 2일, 인터넷에 다른 코드를 이해하는 데 2일이 걸렸다. 문자열 O를 N으로 만들기 위해 추가해야 하는 최소 '문자열'의 개수를 구하는 문제다.우선, 내 머리만으로 해결하진 못 했다. 처음에는 단순하게 앞에서부터 비교하면서 O에 없는 문자를 카운트 했다.연속 여부를 고려해 문자열 개수를 카운트 했다. (틀린 방법이니 자세히 설명하진 않겠다.) 그리고 2차원 표에 O[:i] 를 이용해 N[:j] 를 만드는 데 필요한 최소 문자열 개수를 구했다.근데 정말 이리보고 저리봐도 규칙을 끌어낼..
Algorithm/DP
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DP와 DFS 문제다. DFS를 통해 경로를 탐색하고, 돌아오는 길에 경우의 수를 저장해 값이 존재하는 경우 더 탐색하지 않는 DP를 이용한다. DFS의 return 조건은 도착지에 도달 했을 떄, 이미 방문한 적이 있을 때다. 모든 경로의 전체를 탐색하면 당연히 시간초과가 나기 때문에 이미 방문한 적이 있을 경우에는 탐색을 멈춘다. 탐색을 멈추고, 해당 칸에 저장된 값을 현재 칸에 더한다. 그렇게 쭉..
https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net DP와 Greedy 문제다. 제한된 성냥개비를 모두 이용하여 만들 수 있는 가장 작은 수와 가장 큰 수를 찾는 문제다. 자릿수가 커질 것이기 때문에 숫자가 아닌 문자열을 이용해 계산했다. 가장 큰 수의 경우 자릿수를 제일 크게 늘려야 한다. 1을 만들 때 2개가 필요하고 7을 만들 때 3개가 필요하므로 두 개만을 이용해 홀수 짝수인 경우를 고려했다. dp[2] = "1", dp[3] = "7" 만 초기값..
https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net DP 문제다. 파일을 합치는 데는 두 파일의 무게의 합 만큼의 비용이 들고, 이 비용을 최소화 하는 문제다. 파일을 합칠 때는 연속한 두 개를 선택하여 합칠 수 있다. 처음 생각한 방법은 1차원 배열을 이용해 최소의 비용을 찾아나가는 것이다. 1번 파일부터 n-1번 파일까지 고려된 최소 비용에 n번 파일을 합치는 비용을 고려했다. 1 2 3 4 라는 파일이 있는 경우 3까지 계산이 됐다고..
https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제다. 원형 칸에서 나란하지 않은 k개를 고르는 경우의 수를 구하는 문제다. 몇가지 계산하다보니 바로 규칙을 찾을 수 있었다. 행이 n, 열이 k일 때 아래와 같은 표를 그릴 수 있다. 1 2 3 4 4 4 2 0 0 5 5 5 0 0 6 6 9 2 0 7 7 14 7 0 표를 통해 dp[i][j] = dp[j - 1][i] + dp[j - 2][i - 1]와 같은 점화식을 세울 수 있다. #include usi..
[https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net DP와 누적합 문제다. 해당 칸을 기준으로 왼쪽 위쪽으로 존재하는 숫자들의 개수를 세어 배열에 저장한다. 배열은 3차원 배열로 행렬크기에 1~10의 개수를 각각 저장할 수 있는 11의 크기다. 검정색 부분까지의 누적합을 구하기 위해서는 빨간 부분 + 파란 부분 - 보라 부분을 해야한다. 빨간 부분에도 파란 부분에도 보라 부분이 포함되어 있기 때문에 중복 계산되므로 한 번 빼야..
