2019.10.08 L풀이 추가
(생각날때마다 코드, 문제 추가 하겠습니다)
(조금만 일기를 적도록.. 하겠읍니다.. 문제 설명을 보실 분은 스크롤을 쭈욱 내려주세요)
그동안 코드포스, 코드잼 등에 가볍게 참가했었던 반면 2달 정도 전에 있던 UCPC를 포함해서 두 번째로 정신 차리고 긴장했던 ICPC Regional 예선을 오늘! 보았습니다.
작년에 프로그래밍 알고리즘 영역에 들어선 이후로 끊임없이 들어왔던 대회였기 때문에
참여해서 어느 정도 성장했는지 확인하고 싶은 마음이 제일 컸었습니다.
준비 기간 동안을 조금 이야기하자면
<기 - 3월>
- 같이 공부하던 친구(yj)와 대회에 대한 이야기가 나왔습니다.
- 둘 다 주전공이 컴과가 아니었으므로 팀원을 구하기 너무 힘들었습니다.
- 아마 준비기간 중 두 번째로 힘들었을 겁니다.(첫 번째는 곧 나옵니다.)
<승 - 3월 중순 ~ 8월 말>
- 다행히 후배 중 먼저 컴과 공부를 시작한 동생(jh)을 꼬드겨 팀을 꾸렸습니다.
- 주 2회 정도 만나 하루는 고급 알고리즘 조사, 발표, 문제풀이를 했고, 하루는 문제 set을 시간 잡고 풀었습니다.
- 다들 가벼운 마음으로 시작했어서 그런지 빠진 날이 좀 있었습니다.(반성)
<전 - 8월 말 ~ 9월 중순>
- jh가 휴학한 것을 알아버렸습니다;;;;;;;;;;;;;;;;
- 처음에 듣고 너무 자연스러워서 전혀 이상함을 몰랐습니다.
- 팀 등록하려는데 머리가 아프더군요(이때가 진짜 미치는 줄 알았습니다. 별의별 상상 다함)
- 같이 공부를 시작하던 형이 여기저기 알아봐 주었지만 유학 가신 다던 분, 취준 하시던 분 등.. 몇 분 놓쳤습니다 ㅠㅠ
- 결국 또 저희 과 동기분께 부탁을 하여 접수 마지막 날 구할 수 있었습니다 ㅎ
- 동기 분이 알고리즘을 각 잡고 공부하신 분이 아닌 탓에 문제 해석 + 아이디어 제공 + 수학 문제 풀이 등의 역할을 해주시게 됐습니다.
<결 - 9월 말 ~ 10월 오늘>
- 문제는 셋이 같이 하던 프로젝트가 있었는데 끝나질 않았습니다.
- 팀 연습을 빼고라도 프로젝트 빨리 끝내자 하며 하던 프로젝트는 결국 대회 6일 전, 임시 중단을 선언했습니다.
- 결국 대회 전, 딱! 2번 .. .. 팀 연습을 할 수 있었습니다.
- 결국 팀 노트도 제대로 맞추지 못하고 각자 페이지 할당을 해 만들어오자 하고 만났습니다.
- 대회 끗
이렇게 기승전결이 완벽할 수가 ;;;
써놓고 보니 좀 절실하지 않았던 것 같습니다 죄송합니다ㅠ
많은 후회가 됩니다.
- 후배에게 규정에 대해 좀 더 자세히 설명해줄걸
- 아무리 바쁘고 힘들었어도 팀 연습은 꾸준히 할걸
- 문제 좀 더 풀어볼걸
조금만 한다던 소리가 되게 길어졌네요;;;
----------------------------------------------------------------------------------------------------------------------
[대회 이야기]
저희 팀의 컨셉은
1. 각자 문제 할당
2. 쉬운 문제 각자 알아서 해결
3. 특정 알고리즘에 특화된 사람에게 문제 추천 후, 알고리즘 상의
대충 이런 식으로 잡혀있었습니다.
하지만 위에서 말했듯이 팀원이 급히 바뀌었고 기존 컨셉을 유지하기가 힘들었습니다.
결국 오늘 컨셉은
1. 각자 문제 할당
2. 이후 과정
동기 분이 문제 해석, 아이디어 제공, 문제 설명 등
jh가 문제 풀이 방향, 알고리즘 제시
제가 코더, 문제 풀이 방향, 알고리즘 제시
이런 식으로 갔습니다.
(제가 컴퓨터 자리에 앉아버린 탓에? 아무튼 대충 코더가 되어버린 탓에 문제를 많이 못 봤고 그만큼 생각을 할 시간이 적었습니다.)
대회 도중에는 서버 렉이 너무 심했습니다.
등록 문제 AC 받아내는데만 5분 넘게? 걸렸던 걸로 기억합니다. 이 놈의 서버 렉.. 이때부터 뭔가 좋지 못했습니다.
결국 대회 시간은 30분 연장됐고 90분? 그 앞뒤로 해서 문제 채점이 진행되지 않고 pending상태로 남아있어서
AC인지 WA인지도 알 수 없었습니다.
그냥 느낌적인 느낌으로 AC이겠지 하고 코드 제출하고 다음 문제로 넘어갔었는데 이게 진짜 결정적인 패인이었습니다...
(디버깅을 잘하자..!)
대회 내용으로는
I -> H -> B -> C -> L -> K -> J -> L 순서로 제출했고
마지막 3문제는 대회가 끝나고도 몇 시간 동안 pending상태였고,
저희는 뇌 속으로 7 솔브 또는 6 솔브는 되겠다 생각하고 있었습니다.
하지만 ^^ 앞의 4문제만 맞고 4 솔브로 마무리했습니다.. 망할 pending
----------------------------------------------------------------------------------------------------------------------
[문제 소개]
(문제 설명은 푼 순서대로 하겠습니다.)
I. Registration
전통적인 등록 문제입니다.
소개를 하지 말까 하다가, 이 이야기는 해야겠어서 ㅎ
진짜 긴장 안 하고 대회 빨리 끝나라 이러고 있었어요.
그런데 이 문제 만나서 비번 생각 안나는 순간 긴장 급 가득 되고 손 떨리고 하더라고요..
줄 바꿈 안 해서 틀릴 뻔 암튼 그렇다고요
H. Four Squares
(문제 설명)
Input으로 주어지는 n을 몇 개의 제곱수의 합으로 표현하고 싶다. 그때, 최소한의 개수로 표현할 수 있는 개수를 구하라!
(문제 풀이)
그냥 간단한 dp 문제였습니다.
내가 할당받은 문제였는데 긴장한 탓 + 서버 렉 때문에 완전 탐색만 생각나서 정신을 차릴 시간이 필요했습니다.
yj한테 던져줬고, 간단히 dp 식을 구해주었습니다.
dp[i] = i를 합으로 나타낼 수 있는 최소 제곱수의 개수
$$dp[i] = MIN_{1\leq j\leq\left \lfloor \sqrt{i} \right \rfloor}\left \{ dp[i], dp[i-j^{2}] + 1\right \}$$
(코드)
// Team ___---O_
#include <iostream>
#include <algorithm>
using namespace std;
using INF = 1e9 + 7
int dp[50001];
int find(int x) {
if (x < 2) return x;
int res = INF;
for (int i = (int)sqrt(x); i > 0; --i) {
if (dp[x - (i * i)] != -1)
res = min(res, dp[x - (i * i)] + 1);
else
res = min(res, find(x - (i * i)) + 1);
}
return dp[x] = res;
}
int main() {
int n;
cin >> n;
memset(dp, -1, sizeof(dp));
cout << find(n);
return 0;
}B. Balenced String
(문제 설명)
n이 주어질 때, n 길이의 0, 1로 이뤄진 string의 경우의 수를 구하여라.
단, 해당 string은 다음 조건을 만족한다.
$$\forall \,1\leq i\leq n, \: \:\:\left|0's \: count-1's\:count\right|\leq 1\:in\:1\sim i $$
(문제 풀이)
스코어 보드에 이 문제가 꽤나 올라오길래 C를 코딩하면서 yj에게 풀라고 줬던 문제였습니다.
일단, 문제를 분석해보자면,
string의 길이가 짝수일 때는 0과 1의 개수가 같아야 합니다. 홀수일 때는 0이 1개 더 많거나, 1이 1개더 많습니다.
즉, n길이의 string을 만들기 위해 길이 0부터 키워나간다면
현재 길이가 짝수일 때는, 0 또는 1 무엇이든 붙일 수 있고, 홀수일 때는 현재 개수가 1개 더 적은 수를 붙여줘야 합니다.
그러므로 다음 같은 식을 구할 수 있었습니다.
$$case_{n} = \left\{\begin{matrix}
2^{n/2}\:\:if\:n=even\:number\\
2^{n/2}*2\:\:if\:n=odd\:number
\end{matrix}\right.$$
좀 더 정리를 한다면, 다음과 같이 마무리할 수 있을 것입니다.
$$case_{n} = 2^{\frac{n+1}{2}}$$
나머지 처리만 해주면 끗-
C. Byte Coin
(문제 설명)
초기 자본금이 W만큼 있고 갖고 있는 초기 코인은 0개다.
n일 동안의 코인의 주가 변동을 알고 코인을 자유롭게 사고팔았을 때, n일이 지난 후에 최대로 가질 수 있는 금액을 구하라.
(문제 풀이)
문제를 읽자마자 풀이가 너무 자명했습니다.
싼 날에 사서 비싼 날에 팔자!!
너무 쉽게 생각을 해낸 탓에 설마 예외가 있지 않을까 해서 코딩은 시작하고
yj에게 검증을 맡겼고, yj가 만들어준 예외로 테스트도 할 수 있었습니다.
설명을 해보자면
가격이 떨어지다가 올라가기 시작하면 살 수 있는 만큼 사버립니다.
가격이 올라가다가 떨어지기 시작하면 모두 팔아버립니다.
마지막 날에 코인을 갖고 있으면 모두 팔아버립니다.
끗
----------------------------------------------------------------------------------------------------------------------
L. Two Machines
(문제설명)
N개의 task에 대한 A기계와 B기계의 수행 시간이 주어진다.
이 때, 전체 수행시간은 A기계와 B기계가 각자 맡은 task를 모두 마무리하는데 걸린 시간 중, 큰 값이다.
A기계와 B기계에 task를 적절히 나누어서 전체 수행시간이 최소가 되도록 해라.
(문제풀이)
Knapsack DP 문제입니다.
저도 knapsack으로 풀긴 풀었는데 좀 더 깔끔한 풀이가 있더라고요;;;
더 깔끔한 풀이는 많이 공개돼있을 것이기 때문에 제 풀이를 소개하겠습니다.
저는 이 문제를 백준 사이트에 [평범한 배낭] 이라는 문제와 거의 유사하게 만들어서 풀었습니다.
(http://acmicpc.net/problem/12865)
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.
www.acmicpc.net
(생각 과정)
- A 수행시간의 합이 전체 수행시간(답)이라고 가정(B의 경우도 체크)
- A 에게 모든 task를 몰아주기
- B 에게 task를 적절히 분배해주면서 B 의 수행시간은 늘리고 A 의 수행시간은 줄이기
- A 의 수행시간이 B 의 수행시간보다 많으면서, A의 수행시간이 최소가 되도록 하기
(문제 변형 - 평범한 배낭)
- 배낭의 무게 = 모든 task를 A가 수행했을 때, 시간의 총합(A_total)
- 물건을 넣는 행위 = B 에게 task를 분배
- 물건의 무게(AB_i) = B 의 task 수행 시간(B_i) + 대응되는 A 의 task 수행시간(A_i)
- 물건의 가치 = 대응되는 A 의 task 수행시간(A_i)
물건의 가치 즉, 빼줘야 하는 A 의 수행시간이 최대가 되도록 하려고 합니다.
A_total은 변하면 안되기 때문에 B_i를 늘릴 때, A_i를 빼지 않고 같이 늘려주도록 합니다.
그러면 이제 우리가 할 일은 가방에 넣은 물건의 가치의 합을 최대가 되도록 하면 됩니다.
그렇게 구한 가치의 합의 최대는 빼줘야 할 A의 수행시간들이므로 A_total에서 빼주게 되면
task를 적절히 분배했을 때, 전체 수행시간인 A의 수행시간을 구할 수 있습니다!
이 작업을 B 에 대해서도 수행해주고, 위에서 구한 A의 수행시간과 방금 구한 B의 수행시간 중 작은 값을 출력해줍니다.
말로 풀어서 쓰니 너무 어렵네요;;; 코드 첨부 하겠습니다.
(코드)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define size 251
int main() {
int n,
A[size], B[size], AB[size],
A_total = 0, B_total = 0,
dpA[size][size*size], dpB[size][size*size];
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> A[i] >> B[i];
AB[i] = A[i] + B[i];
A_total += A[i];
B_total += B[i];
}
memset(dpA, 0, sizeof(dpA));
memset(dpB, 0, sizeof(dpB));
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= A_total; ++j) {
if(j >= AB[i]) dpA[i][j] = max(dpA[i-1][j], dpA[i-1][j-AB[i]] + A[i]);
else dpA[i][j] = dpA[i-1][j];
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= B_total; ++j) {
if(j >= AB[i]) dpB[i][j] = max(dpB[i-1][j], dpB[i-1][j-AB[i]] + B[i]);
else dpB[i][j] = dpB[i-1][j];
}
}
int res, Max_A = 0, Max_B = 0;
for(int i = 0; i <= A_total; ++i) Max_A = max(Max_A, dpA[n][i]);
for(int i = 0; i <= B_total; ++i) Max_B = max(Max_B, dpB[n][i]);
res = min(A_total - Max_A, B_total - Max_B);
cout << res;
}
물론 아는 사람은 알겠지만 이러면 메모리가 너무너무 커져서 별로입니다.
글이 너무 길어지는 것 같지만, 다음과 같이 하면 메모리를 줄일 수 있습니다.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define size 251
int main() {
int n,
A[size], B[size], AB[size],
A_total = 0, B_total = 0,
dpA[size*size], dpB[size*size];
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> A[i] >> B[i];
AB[i] = A[i] + B[i];
A_total += A[i];
B_total += B[i];
}
memset(dpA, 0, sizeof(dpA));
memset(dpB, 0, sizeof(dpB));
for(int i = 1; i <= n; ++i)
for(int j = A_total; j >= AB[i]; --j)
dpA[j] = max(dpA[j], dpA[j-AB[i]] + A[i]);
for(int i = 1; i <= n; ++i)
for(int j = B_total; j >= AB[i]; --j)
dpB[j] = max(dpB[j], dpB[j-AB[i]] + B[i]);
int res, Max_A = 0, Max_B = 0;
for(int i = 0; i <= A_total; ++i) Max_A = max(Max_A, dpA[i]);
for(int i = 0; i <= B_total; ++i) Max_B = max(Max_B, dpB[i]);
res = min(A_total - Max_A, B_total - Max_B);
cout << res;
}----------------------------------------------------------------------------------------------------------------------
또 공부해서 추가하겠습니다.