마지막 정보올림피아드를 다녀왔습니다.

---

안녕하세요, 계략입니다.

일상...이랄까요. 그런 글입니다.

---

블록체인이라는 특성상 개인정보를 올리기를 꺼려했는데
생각해보니 이정도까지는 괜찮지 않을까... 했습니다.

저는 고등학교 3학년입니다!

이런... 슬프네요.

그리고 정보과학이나 프로그래밍 쪽으로 관심이 있습니다.

그런고로 옛날부터 쭈욱, 한국정보올림피아드에 참가해 왔습니다.

지금까지 두 번, 전국대회에서 은상을 수상했습니다.
사실 그런 것 치고는 제 프로래밍 실력이 뛰어나다고 생각하진 않아요.
다른 수상자들을 보면 엄청 신기할 따름입니다.
약간의 꼼수라면 꼼수를 잘 쓴 덕분이죠.

어찌 되었든, 고3인지라 올해가 마지막이었습니다.
그래서 그걸 준비한다고 1주정도 스팀잇에 글을 올리질 못했네요.
그보다도 감기에 걸렸던게 컸습니다. 아직도 다 안 나았어요. ㅠㅠ

---

정보올림피아드는 프로그래밍 경진대회입니다.
절대 검색하는 대회가 아니에요!

초등부 / 중등부 / 고등부 나뉘어서
총 4시간 동안, 4개의 프로그래밍 문제를 풀게 됩니다.
최근 들어서는 4개 모두 100점으로 배점이 동일합니다.
400점 만점이고, 보통 1등은 350점 내외를 받습니다.
가끔 가다가 중간에 400점을 받고 나가는 괴물도 있습니다

https://www.acmicpc.net/category/55
에서 지난 년도 문제를 보고 풀어보실 수 있습니다. (공식 사이트는 아닙니다)

---

결과부터 말하자면, 마지막 대회의 결과는 좋지 못했던 것 같습니다.
1번부터 4번까지 총 4문제가 출제되고, 각 문제별로 배점은 100점으로 동일합니다.
그런데... 1번을 포함해서 100점을 받은 문제가 없었어요.
아무래도 동상을 받게 될 것 같습니다.

실력의 한계를 체험하고 온...
아팠던 것도 있겠지만, 실력적인 한계였던 것 같습니다.

---

그래도 대부분이 가장 어려웠을거라 생각하는 4번 문제에서 의외의 성적을 거둔 것 같습니다.
프로그래밍 관련해서 관심 있으신 분들은 한번 풀어보셨으면 합니다.
아래는 기억에 의존한 4번 문제입니다.

조개 줍기(수산시장)

N*N개의 격자로 된 마을이 있습니다.
각 마을에는 주민이 1명씩 살고 있고,
가장 왼쪽 위의 마을에는 수산시장이 있습니다.

환경보호를 위해 각 마을에서 주울 수 있는 조개의 개수는 제한되어 있습니다.
주민들은 왼쪽 혹은 위쪽으로만 이동하며 조개를 줍습니다.

수산시장이 있는 마을에도 주민이 살고 있으며
수산시장이 있는 마을에서도 조개를 주울 수 있습니다.

생태계 보호를 위해, 공무원은 조개 개수의 제한을 바꾸려고 합니다.
한 번 바꿀 때, 한 마을에서 주울 조개 개수의 제한을 1개 줄이거나 1개 늘리는 것만 가능합니다.

맨 처음의 상태와, 바뀐 제한에 따라 수산시장에 팔리는 조개 개수의 합의 최대값을 구하세요.

---

입력

첫 번째 줄에 격자의 크기와 제한을 바꾸는 횟수 N이 주어집니다.

그 다음 N개의 줄에는 각각의 마을에 대해 주울 수 있는 
조개 개수의 제한을 나타내는 수 K가 공백으로 구분되어 N개 입력됩니다.

그 다음 N개의 줄에는 주울 수 있는 조개 개수의 제한을 바꾸는 행동이 입력됩니다. 
첫 글자가 U일 경우 1개 늘리는 행동, D일 경우 1개 줄이는 행동입니다.
글자 뒤에는 마을의 좌표가 공백으로 구분되어 주어집니다.
왼쪽 위의 마을은 1 1, 오른쪽 아래의 마을은 N N입니다.

---

출력

첫 번째 줄에는 초기 상태에 대해, 수산시장에서 팔리는 조개의 최댓값을 출력하세요.
두 번째 줄부터 N개의 줄에는 제한을 바꾼 뒤, 수산시장에서 팔리는 조개의 최댓값을 출력하세요.

---

입력 예시
2
1 5
3 2
U 1 1
D 2 2

---

출력 예시 (괄호 안은 출력 X)
19 (1+6+4+8)
23 (2+7+5+9)
22 (2+7+5+8)

---

제약 조건
1<=N<=2000
1<=K<=1000 (확실하지 않습니다)
조개의 제한이 음수가 되는 경우는 없음
1초 내에 결과를 출력해야 함
메모리 512MB 이하 (확실하지 않습니다)

---

너무 대충 적은 것 같긴 하지만...
일단 제가 봤을 때, 초기 상태에 대해 값을 구하는 건 전형적인 다이나믹 프로그래밍(DP) 문제였습니다.
문제는 그 다음부터죠.

DP로 잘 푼다면, O(N^2)안에 초기 값을 구할 수 있을 겁니다.
그런데 바꾸는 행동이 N개니까, 모두에 대해 DP를 쓰면 O(N^3)으로 시간이 초과됩니다.

그렇게 풀면 시간이 대략 13점이 나는 관계로 약간의 최적화를 감행했습니다.

초기 값을 구하는 DP를 할 때, 위쪽으로 가면 큰지 왼쪽으로 가면 큰지를 메모해뒀습니다.
그 뒤에 숫자를 1 키우거나 줄임에 따라서 그거에 대한 경우를 모두 처리하는(...) 방식으로 말이죠.
그렇게 해서 43점 가량을 받았습니다.
코드가 400줄 이상은 나왔더라고요.
정보올림피아드 문제를 풀면서 가장 길게 적은 코드였던 것 같습니다.
다만 저것보다 시간을 더 줄일 방법은 아직도 잘 모르겠습니다.
댓글로 토의를 해 본다면 어떨까요...?

---

여하튼, 좀 아쉽긴 하지만 마지막 정보올림피아드를 마쳤습니다.
몸 상태도 그렇고, 결과도 그렇고 썩 좋지만은 않지만
그래도 4번 문제에 저런 시도를 했고 부분의 성공을 거뒀다는 점과
제 한계를 제대로 느꼈다는 점에서 좋았던 것 같습니다.

읽어주신 분들께 감사드리면서,
저 4번 문제의 정해진 시간 내에 풀 수 있을 O(N^2 log N)코드를 알 것 같으신 분은 댓글로 알려주셨으면 합니다(...)