BOJ(53)
-
BOJ 2923 : 숫자 게임
https://www.acmicpc.net/problem/2923 문제에서 10)로 포인터들을 움직이면서 그리디하게 찾아주면 된다 코드
2021.08.06 -
BOJ 15311 : 약 팔기
https://www.acmicpc.net/problem/15311 15311번: 약 팔기 첫 번째 줄에 동규의 최대 약 요구량을 나타내는 정수 N ($=1\, 000\, 000$) 이 주어진다. www.acmicpc.net 재밌는 문제다. 왠만하면 풀이를 보지 않는 걸 추천한다. n 1000*1000 + 1*1000이므로 배열을 1 1000개와 1000 1000개로 채우면 모든 수를 만들 수 있다. 코드
2021.08.04 -
BOJ 1066 : 에이한수
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일때 갯수 라고 정의하..
2021.08.03 -
BOJ 1637 : 날카로운 눈
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)이 최초로 홀수가 되는 순간을 이분탐색으로 찾으면 된다. 코드
2021.08.03 -
BOJ 21061 : Beautiful Permutation
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..
2021.08.03 -
BOJ 22344 : 그래프 균형 맞추기
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값이 나오는 경우가 있다. 이를 주의하..
2021.08.01