https://www.acmicpc.net/problem/1066 1066번: 에이한수 첫째 줄에 N자리이면서 진짜A한수의 개수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 관찰이 재밌고 어려운 문제이다. 내가 문제 풀 당시에 관찰한 것은 -진짜 A한수에서 A의 자릿수가 비내림차순하게 만드려면 무조건 수열로 분할했을때 모든 수열이 비내림차순이여야 되는것이다. -A한수는 A+1한수이다. (if A 찐A한수는 등차수열 그룹의 갯수의 최솟값이 A인 A한수다. -A>9일때 답은 0이다. 이를 이용해 dp로 풀면 dp[i][j][k][d] = i번째 자릿수 차례, 등차수열 그룹 수가 j, i번째 자릿수가 k, 이전수가 속한 그룹의 등차가 d일때 갯수 라고 정의하..

https://www.acmicpc.net/problem/1637 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 아주 재밌는 문제이다. 보기 전에 꼭 혼자서 시도해보고 오길 바란다. f(n) = n 이하의 수들의 갯수 라고 한다면 f(n)이 최초로 홀수가 되는 순간이 답일 것이다. f(n)이 최초로 홀수가 되는 순간을 이분탐색으로 찾으면 된다. 코드

https://www.acmicpc.net/problem/21061 21061번: Beautiful Permutation A permutation $a_0, a_1, \ldots, a_{n - 1}$ of $0, 1, \ldots, n - 1$ is said to be beautiful if the sequence $b_0, \ldots, b_{n - 1}$ defined as $b_i = |a_i - i|$ is also a permutation of $0, \ldots, n - 1$. Given $n$, construct a beautiful permutation o www.acmicpc.net 상당히 힘들었던 문제. 풀고 나서 보는 걸 추천한다. 일단 n%4의 값이 0,1일때만 성립하고, 아니면 N..

https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 개인적으로 이번 KOI 고등 1번 난이도>>>>>>>이번 KOI 고등 2번 난이도라고 생각한다. 먼저 모든 정점의 가중치를 x+a나 -x+b로 표현 가능하다. 이를 통해 가중치의 합의 최소 = 절댓값 함수에서의 최솟값을 이용하면 된다. 이때 사이클이 있을때의 예외를 잘 처리해야 하는데, 사이클이 있을 때 어떤 임의의 두 인접한 정점에서 유일한 x값이 나오는 경우가 있다. 이를 주의하..

22348번: 헬기 착륙장 (acmicpc.net) 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net dp[i][j] = i개의 동심원, j개의 빨간 페인트를 이용했을 때 만들 수 있는 동심원 갯수 라고 두면 점화식은 이렇다 dp[i][j] += dp[i-1][j-i] (헤당 동심원에 빨간색 원을 만들 때) dp[i][j] += dp[i-1][j] (헤당 동심원에 파란색 원을 만들 때) 이때 우리는 만들 수 있는 모든 헬기 착륙장의 갯수를 만들어야 하므로, i

https://www.acmicpc.net/problem/1056 1056번: 수 1부터 시작해서 N을 만들려고 한다. 사용할 수 있는 연산은 아래와 같이 총 3가지이다. 이때, N을 만드는데 사용하는 연산의 최소 횟수를 구하는 프로그램을 작성하시오. 현재 수를 1 증가시킴 (현 www.acmicpc.net 누가 봐도 DP를 이용하는 것이다. dp[i] = i를 만드는데의 최소 연산 수 . a^k