시간 제한 메모리 제한 2초 128 MB 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이 일단 K개의 정수로 N을 만들어냈을 때, K - 1개의 정수로 N - a 를 만든 것과 1개의 정수로 a를 만든 경우의 합과 같다는 것을 알았다. 부분 해를 합해 전체 해를 얻을 수 있으므로 DP를 쓰는 문제인 건 확실하다. 문제는 점화식이 어떻게 되는 건지 정리가 ..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 기초적인 다이나믹 프로그래밍 문제다. 입력에서 테스트케이스 개수가 100,000까지 주어지는 걸로 봐서는 절대 매번 따로 연산하는 방법으로 해결할 수 없다. 두 좌표가 주어지면, 그 좌표를 기준으로 미리 처리된 값으로 연산해 연산 횟수를 일정하게 유지하도록 해야 하는 문제. 입력은 N*N 정사각행렬 형태로 주어진다. 처음 문제를 봤을 때는 (x1, y1)부터 개행하며 (x2, y2)까지의 모든 항을 합하는 문제인 줄 알았..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS는 가장 긴 공통 부분 수열을 찾는 유형의 문제를 이르는 말인 것 같다. 우선 풀이는 완전탐색(브루트포스), 동적계획법이 가능하다. 어느 블로그를 찾아보니 LCS가 두 가지 문제 유형으로 나뉜다고 한다. 1. Longest Common Substring 2. Longest Common Subsequence 이 문제는 2번이다. 1번은 가장 긴 공통..

3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 풀이 #idea 0 ~ N - 1 까지의 가로, 세로에서 색깔 바꾸기 가능 각 행, 열에 가장 많은 연속된 글자 찾기 색깔 바꾸기는 한 번만 실행하므로 불필요한 반복을 줄이기 위해 전체 행, 열의 원래 연속 데이터를 확인 #구현방안 색깔 바꾸기 k 와 k + 1의 색깔이 같은 경우, 바꿀 수 없음 최대 연속 데이터 찾기 초기 데이터에서 최대 연속 데이터 먼저 확인 행에서 바꾸면 해당 행과 바뀐 데이터의 열의 최대 연속 데이터 확인 열에서 바꾸면 해당 열과 바뀐 데이터의 행의 최대 연속 데이터 확인 using System; class program { static int N, co..

6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 풀이 #idea 마지막 해는 M과 N의 최소공배수다. 현재 해를 K라고 할 때, K = M * a + x = N * b + y 부정방정식의 최소 해 #구현 방안 M과 N의 최소공배수 구하기 1~200까지의 소수 데이터를 만들어놓고 공통인수 찾기 두 수 중 작은 수를 n배 하며 같은 수가 나올 때까지 반복하기 부정방정식의 최소 해 구하기 초기 값 지정 a, b = 0 M * a + x 와 N * b + y 중 작은 쪽부터 a나 b를 1씩 증가시키기 M * a + x ..

1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 풀이 #case 숫자 버튼 없이 ＋, － 버튼으로만 이동하는 경우 (채널을 바꾸지 않아도 되는 경우를 포함한다.) 누를 수 있는 버튼으로 이동하고자 하는 채널과 근사한 값들을 만들어 ＋, － 버튼으로 이동하는 경우 자릿수가 같은 숫자로 출발하는 경우 자릿수가 다른 숫자로 출발하는 경우 (예. 0, 1이 고장 났을 때 999에서 1000으로 이동) #구현 방안 1행 입력값과 100의 차 구하기 1행 입력값보다 큰 값으로 만들기 1행 입력값보다 작..

2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 에라토스테네스의 체를 생각하며 가장 작은 수부터 리스트에 추가하고 동시에 추가된 수들을 회전시켜 얻은 시계수가 아닌 수들은 걸러내는 방법을 적용했다. 1111을 가장 먼저 리스트에 추가하면 1111을 회전시켜 얻은 1111, 1111, 1111을 확인한다. 모두 같으므로 패스. 1112는 걸러지지 않았으므로 리스트에 추가한다. 1121, 1211, 2111을 제외한다. 이하 반복 입력된 수를 돌려 얻은 시계수가 리스트의 몇번째 항목인지만 확인해 출력하면 끝. using System; us..

11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net IDEA 처음 봤을 때는 쉬운 정렬 문제구나 했다. 리스트를 만들었고 그냥 정렬해서 출력했다. 대신 List 형식의 요소를 꺼내올 때 하나씩 따로 꺼내오는 걸 몰라서 지저분하게 String 메소드를 이것저것 갖다 붙이게 됐다. 너무 맘에 안들어..하던 와중에 2차원 배열의 정렬 방법을 다른 분의 코드에서 찾았다. 리스트에서 특정 항목을 기준으로 배열하는 방법인데 엑셀에서 필터 적용하는 것과 비슷한 개념인 것 같..