PS(64)
-
BOJ 1187 : 숫자 놀이
https://www.acmicpc.net/problem/1187 1187번: 숫자 놀이 2N - 1개(N = 2k, 1 ≤ k ≤ 10)의 정수가 있다. 주어진 수 중 임의로 N개를 뽑았을 때 이 합이 N으로 나누어떨어지도록 하는 N개의 수를 출력하는 것이 문제이다. 답이 여러 개일 경우 아무거나 한 개 www.acmicpc.net 문제가 아주 좋으니 충분히 고민해보고 풀길 바란다. 먼저 이 문제에서 안되는 경우가 있는지 확인해보자. 일단 k=1일때는 비둘기집 원리에 의해 항상 답이 있다는 것을 알 수 있다. 그렇다면 여기서 귀납법을 이용해보자. k = n-1일때 무조건 성립한다고 가정하자. k = n일때, 2^(n+1)-1개의 원소가 있을것이며, 이를 2^(n-1)개의 원소가 들어가 있는 그룹 3개와..
2021.08.13 -
BOJ 16764 : Cowpatibility
https://www.acmicpc.net/problem/16764 16764번: Cowpatibility Here, cow 4 is not compatible with any of cows 1, 2, or 3, and cows 1 and 3 are also not compatible. www.acmicpc.net 가능한 조합을 모두 맵에 저장해놓고 포함 베제 원리를 이용하면 된다. (가능한 모든 조합 - 1개짜리 + 2개짜리 - 3개짜리 + 4개짜리 - 5개짜리) 자세한건 코드 참고.
2021.08.13 -
BOJ 6171 : 땅따먹기
https://www.acmicpc.net/problem/6171 Naive한 dp로 먼저 생각해보자. dp[i] = i번째 땅까지 샀을 때의 비용의 최솟값 dp[i] = min(dp[j-1]+max(w[k])*max(h[k])) (0
2021.08.08 -
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 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