https://www.acmicpc.net/problem/19568 이 문제를 풀기 전, 약 팔기 문제를 먼저 풀고 오는 것을 추천한다. 약 팔기 아이디어를 2D로 확장시킨 문제이다. (15,15)를 중심으로 1, 15, 15^2, 15^3을 상하좌우로 한 줄에 펼쳐놓으면 50000 이상까지 찾을 수 있다. 코드

이번 2월에 나는 비요뜨(gunwookim)과 함께 블롭컵을 개최하였다. -문제별 후기 미리 말하지만, 제가 내지 않은 문제들은 후기를 제대로 하지 못하는 점에 대해 양해 부탁드립니다..ㅠㅠ A. blobnom 비요뜨가 낸 문제다. 잘 만들어서 꼭 내고 싶다 하길래 그냥 내게 냅뒀다. 이 문제는 원래 B번이었는데, 예전 A가 더 어렵다는 판단이 많아서 얘가 A가 되고 예전 A가 B번으로 갔다. 지문을 쓸 때 예전에 어떤 검수자가 보내준 짤(blobnomnomnom...)이 생각나서 그걸 컨셉으로 지문을 썼고, 쓰는데 매우 힘들었던 걸로 기억한다.... 대회 시작했을 때 다들 저걸 틀려서 데이터가 잘못되었을까봐 조마조마했었다. 다행히 다들 코너 케이스에 의해 WA를 받은 것이었다. 검수진 중 대다수가 이 ..

문제 링크 그림을 그리면서 관찰을 해보자. 먼저 n번째 원판들이 1->3으로 갈 때 옮기는 횟수는 n=1일 경우 3, n>1일 경우 2^(n+1)임을 알 수 있다. 그렇다면 이를 n번째 원판들까지 있다고 할 때 옮기는 총 횟수를 식으로 나타내보자. 2^(n+1)+2^n+2^(n-1).....+2^3+3 = 2^(n+1)+2^n+2^(n-1).....+2^3+2^2+2^1+2^0-4 = 2^(n+1)+2^n+2^(n-1).....+2^3+2^2+2^1+2^0+1-5 = 2^(n+2)-5 가 된다. 이제 이걸 계산해주면 되는데, 아주 큰 수를 계산한 나머지를 요구한다. 큰 수 계산, 거듭제곱 계산에는 Python이 더 유리하므로 파이썬으로 풀었다. C++로 한다면, n의 최대가 10^6이므로 그냥 O(n)으..

https://www.acmicpc.net/problem/2516 2516번: 원숭이 첫째 줄에는 원숭이들의 수를 나타내는 하나의 정수 N이 주어진다. 단, N은 3이상 100,000이하의 정수이다. 둘째 줄부터 N개의 줄에는 1번부터 번호순서대로 각 원숭이에 대해 앙숙관계에 있는 원숭 www.acmicpc.net 신기한 그리디 문제다. 모든 원숭이를 한 우리에 모아두고 앙숙관계가 2마리 이상인 원숭이들을 다른 곳으로 옮겨놓는 방식으로하면 된다. i) 옮길 원숭이가 없다면 모든 원숭이에 대해 같은 우리에 앙숙관계인 원숭이가 1마리 이하임을 의미하므로 문제의 답을 찾을 수 있다. ii) 옮기는 경우가 있다면 옮기고 나서 앙숙관계인 원숭이가 1개 이상 줄어든다. 그러므로 이런 상황은 통틀어서 총 3n번까지 ..

www.acmicpc.net/problem/10836 진짜 쉬운 문제. 관찰을 하면 바로 해가 떠오르는 문제이다. 이게 왜 초등 4번? (i, j) (i>0 && j>0)인 칸들은 자신의 바로 위의 칸과 같다는 사실을 관찰하면 풀린다. 고등부에 있는 여왕벌은 차원이 다르게 미쳤다 #include #define sanic ios_base::sync_with_stdio(0) #define MOD 1000000 using namespace std; typedef long long ll; typedef pair p; const ll MEM = 4006; const ll INF = 1e9+7; ll n,m,d,t; ll dp[MEM]; int main() { sanic; cin.tie(0); cout.tie(0)..