PS/Ad-hoc & Constructive(7)
-
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 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 -
BOJ 14864 : 줄서기
BOJ 14864 : 줄서기 14864번: 줄서기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 학생 수 N (1 ≤ N ≤ 100,000)과 순서쌍의 수 M (0 ≤ M ≤ 1,000,000)이 공백으로 분리되어 주어진다. 일렬로 서 있는 학생들을 순서대로 학생1, 학 www.acmicpc.net i번째 숫자카드보다 작은 숫자카드의 갯수를 c[i]라고 하자. 그렇다면 순서쌍 (x,y)에 따르면 x가 y보다 더 큰 숫자카드이므로 c[x]는 1 증가, c[y] = 1 감소한다. 이를 계속해주면 되고, 같은 수의 숫자카드는 없기 때문에 값이 같게 나올경우 안되는 경우이므로 -1을 출력하면 된다. 코드
2021.05.11