https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net DP와 Greedy 문제다. 제한된 성냥개비를 모두 이용하여 만들 수 있는 가장 작은 수와 가장 큰 수를 찾는 문제다. 자릿수가 커질 것이기 때문에 숫자가 아닌 문자열을 이용해 계산했다. 가장 큰 수의 경우 자릿수를 제일 크게 늘려야 한다. 1을 만들 때 2개가 필요하고 7을 만들 때 3개가 필요하므로 두 개만을 이용해 홀수 짝수인 경우를 고려했다. dp[2] = "1", dp[3] = "7" 만 초기값..
Algorithm
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/1999 1999번: 최대최소 첫째 줄에는 세 정수 N, B, K가 주어진다. 다음 N개의 줄에는 행렬이 주어진다. 차례로 1행, 2행, …, N행이 된다. 각 줄에는 N개의 정수가 주어지며, 이는 차례로 1열의 성분, 2열의 성분, …, N열의 성 www.acmicpc.net 자료구조 문제다. N x N 행렬에서 B x B 크기 만큼에서 최대 최소를 찾아 그 차를 구하는 것이다. 모든 질문에 대해 B의 크기가 같다는 것을 못 보고 DP를 활용해 각각 최대 최소를 저장하는 배열을 만들려 했다. 그러나 B의 크기가 항상 동일하다는 것을 알고 DP가 아니라는 것을 알았다. 범위의 크기를 보니 무지성으로 탐색을 해도 괜찮을 것 같았다. 주의할 점은 중복..
https://www.acmicpc.net/problem/15926 15926번: 현욱은 괄호왕이야!! 첫 번째 입출력에서, 맨 처음 위치부터 4개를 잘라낸 (())가 가장 긴 올바른 괄호 문자열이다. 두 번째 입출력에서, 6번째 위치부터 8개를 잘라낸 ()((()))가 가장 긴 올바른 괄호 문자열이다. www.acmicpc.net 스택 문제다. 올바른 괄호 부분 문자열 중 길이가 가장 긴 것을 찾는 것이다. 처음에는 일반 괄호 짝 맞추기처럼 여는 괄호는 스택에 넣고 닫는 괄호를 만나면 스택에서 여는 괄호를 빼는 방법을 택했다. 이 때, 스택에 넣고 뺄 때마다 카운트를 했다. 닫힌 괄호를 만났을 때 스택이 비어 있으면 해당 사이즈 만큼 카운트를 줄였다. ((() 와 같이 열린 괄호가 많은 경우 반례가 생..
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문자열과 백트래킹 문제다. 모든 언어는 "anti"로 시작되고, "tica"로 끝난다. 모든 언어는 8글자 이상이고 15글자 이하다. 학생들은 K개의 글자로만 이루어진 단어만 읽을 수 있다. 즉, K개에 a, n, t, i, c은 필수로 포함된다. a, n, t, i, c는 항상 포함되므로 별도로 확인할 필요가 없기 때문에 문자열을 입력 받을 때 앞뒤 고정 부분을 제거하고 저장한다. K가 ..
