Constructive(6)
-
BOJ 19568 : 직사각형
https://www.acmicpc.net/problem/19568 이 문제를 풀기 전, 약 팔기 문제를 먼저 풀고 오는 것을 추천한다. 약 팔기 아이디어를 2D로 확장시킨 문제이다. (15,15)를 중심으로 1, 15, 15^2, 15^3을 상하좌우로 한 줄에 펼쳐놓으면 50000 이상까지 찾을 수 있다. 코드
2021.11.16 -
BOJ 12935 : 트리와 경로의 길이 2
https://www.acmicpc.net/problem/12935 위 그림 같이 풀면 된다. 10000까지 돌려본 결과 노드의 갯수가 딱 500개로 맞추어지므로 이는 항상 성립한다. n,m+1을 브루트포스하여 구하고, 이를 저 그래프에 맞게 출력하면 된다. 딱 500개로 맞추어지는게 좀 신기한 문제였다. 코드
2021.11.16 -
BOJ 1201 : NMK
https://www.acmicpc.net/problem/1201 n+1m*k이면 안되는 경우이므로 걸러준다. k,k-1,k-2....1, 2k,2k-1,2k-2.....k+1,3k......min(n,mk).....(m-1)k+1 이런식의 수열을 만들면 된다. 증가 수열 : k, 2k, 3k....min(n,mk)으로 총 길이가 m이다. 감소 수열 : 각각 감소수열의 길이가 k개 혹은 그 이하이므로 최대 길이는 k이다. 아이디어가 좀 신기해서 재밌고 기억에 많이 남는 문제이다. 코드
2021.11.16 -
BOJ 2516 : 원숭이
https://www.acmicpc.net/problem/2516 2516번: 원숭이 첫째 줄에는 원숭이들의 수를 나타내는 하나의 정수 N이 주어진다. 단, N은 3이상 100,000이하의 정수이다. 둘째 줄부터 N개의 줄에는 1번부터 번호순서대로 각 원숭이에 대해 앙숙관계에 있는 원숭 www.acmicpc.net 신기한 그리디 문제다. 모든 원숭이를 한 우리에 모아두고 앙숙관계가 2마리 이상인 원숭이들을 다른 곳으로 옮겨놓는 방식으로하면 된다. i) 옮길 원숭이가 없다면 모든 원숭이에 대해 같은 우리에 앙숙관계인 원숭이가 1마리 이하임을 의미하므로 문제의 답을 찾을 수 있다. ii) 옮기는 경우가 있다면 옮기고 나서 앙숙관계인 원숭이가 1개 이상 줄어든다. 그러므로 이런 상황은 통틀어서 총 3n번까지 ..
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 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