티스토리 뷰
Codeforces는 외국 알고리즘 저지 사이트로, 백준처럼 각종 알고리즘 문제를 풀어볼 수 있을 뿐 아니라 주기적으로 대회를 개최하는 걸로 유명한 사이트다. 대회에서 거둔 성적에 따라 레이팅을 얻을 수 있어서, 알고리즘 문제풀이를 즐기는 사람들 사이에선 코드포스 레이팅으로 실력을 가늠하기도 한다... 고 하더라.
나는 딱히 알고리즘 문제풀이가 취미인 사람은 아니고 그냥 취준 하다보니 백준이랑 SWEA 들락거리면서 지금 다니는 곳에서 내주는 과제 정도나 푸는 사람이다. 더구나 내가 알고있던 정보는, 코드포스 대회는 Div. 1이랑 Div. 2 두 개의 부문이 있는데 둘 중에 낮은 레벨인 Div. 2만 해도 3번 문제부터는 백준 solved.ac 기준으로 골드 상위에서 플티 이상급 문제가 튀어나오는 굉장히 수준높은 사이트라는 것이었다. 굳이 가볼 이유도 없었고 엄두도 나지 않았다.
그런데 어제 권태로운 하루를 보내다가 문득 코드포스가 생각이 나서 한번 가입이나 해둘까... 싶어서 들어가봤는데, Div. 4 대회가 처음으로 열린다는 소식을 접하게 됐다.
수준이 어느정도일지 가늠하기는 어려웠지만 Div. 2보다 두 단계 낮은 수준이라면 어쩌면 해볼만하지 않을까 싶었다. 그리고 하루종일 쉬었기 때문에 뭐라도 좀 의미있는 일을 하고 싶었다. 그래서 가입하자마자 등록을 했다.
한국시간으로 5월 9일 23시 35분에 대회가 시작됐다. 문제는 7개, 제한시간은 2시간이 주어졌다. 사이트 구성은 예전 학부 시절에 (교수님의 강요로) 경험해본 적 있었던 ACM-ICPC 대회랑 비슷한 느낌이었다.
결과는... 2문제 풀었다. 생각보다 더 쉽지 않았다. Div. 4가 이 정도 수준이면 Div. 2까지 있었던 시절에 손댔다면 정말 두시간 내내 손가락만 빨고 있었을 것이다.
(Div. 4에 대한 정보를 찾아보다보니 무슨 Div. 4까지 만드냐는 부정적인 의견도 많이 볼 수 있었는데....)
최근에 나름 알고리즘 문제들을 꽤 풀긴 했었다지만 아무래도 삼성 역량테스트 대비에 초점이 맞춰진 문제들을 많이 풀다보니 시뮬레이션은 어느정도 해도 실행시간을 최적화해야 하는 종류의 문제에는 전혀 익숙하지 않은 것 같다. 기업 코테랑 알고리즘 대회는 확실히 스타일이 많이 다른가 그런 생각도 들고...
A. Sum of Round Numbers
N000 형태, 그러니까 0이 아닌 숫자로 시작하고 나머지는 0인 숫자를 Round Number라고 하고 주어지는 숫자를 Round Number들의 합으로 표현하라는 문제.
예를 들어 98050 = 90000 + 8000 + 50이다.
각 자리마다 0이 아니면 그 숫자를 빼낸 다음 뒤에 0이 붙도록 10^n을 곱해줬고, 0이면 그냥 스킵하도록 했다.
첫번째 문제답게 그래도 쉬운 문제가 나오긴 했는데 영어를 너무 오랜만에 봐서 (...) 처음에 딱 보자마자 이해하지 못하고 다른 문제로 넘어갔었다...
public class probA {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
for (int t=1; t<=T; t++) {
String strn = bf.readLine();
int count = 0;
int[] rounds = new int[strn.length()];
for (int i=1; i<=strn.length(); i++) {
if (strn.charAt(i-1) == '0')
continue;
else {
int round = (strn.charAt(i-1) - '0') * (int) Math.pow(10, strn.length() - i);
rounds[count++] = round;
}
}
System.out.println(count);
for (int i=0; i<count; i++) {
System.out.print(rounds[i] + " ");
}
System.out.println();
}
}
}
B. Same Parity Summands
주어지는 숫자 N을 K개 숫자 (단, 모두 홀수 or 모두 짝수) 의 합으로 나타내는 문제이다.
두번째 문제부터 벌써 난관에 봉착했다. N이 K로 나누어떨어진다면야 쉽지만 그렇지 않다면? K로 일단 나눈 다음에 그 주변 숫자를 탐색해보면 될 것 같긴 했는데 짝수, 홀수도 신경써줘야 하고... 그 뒤가 영 떠오르지 않아서 그냥 다음 문제로 넘어갔다. 그리고 풀지 못했다.
C. K-th Not Divisible by n
N, K가 주어지는데 1부터 시작해서 N으로 나누어떨어지지 않는 숫자만 센다고 했을 때 K번째 숫자가 무엇인지를 찾는 문제이다.
바로 생각나는 건 반복문을 1부터 돌면서 N으로 나누어떨어지지 않으면 카운트를 올려주고, 나누어떨어지면 스킵하는 거지만 당연히 시간초과가 났다.
K를 N으로 나누면 1~K까지의 숫자 중에 N으로 나누어떨어지는 숫자가 몇 개 나오는지 찾을 수는 있다. 그런데 K 이후의 숫자 중에도 또 N으로 나누어떨어지는 숫자가 있기 때문에 추가적인 처리가 더 필요한데... 여기서 더 나아가지 못하고 못 풀었다.
D. Alice, Bob, and Candies
사탕 개수가 들어있는 배열이 주어진다. 앨리스는 왼쪽부터 사탕을 먹고, 밥은 오른쪽부터 사탕을 먹으며, 앨리스와 밥이 번갈아가면서 사탕을 먹는다. 이 때 이전에 상대방이 먹었던 개수보다 많이 먹어야 하며, 배열의 각 칸에 들어있는 사탕은 한번에 다 먹는다.
예를 들어서 [3, 1, 4, 1] 이라면 첫 턴에 앨리스가 3개를 먹고, 다음 턴에 밥은 1개를 먹고보니 3개보다 적으니 한칸 더 가서 4개를 더 먹는다. 즉 밥은 5개를 먹는다.
이런 식으로 쭉 갔을 때 끝날 때까지 소요된 턴 수와 각자 먹은 사탕 수를 출력하는 문제이다.
나왔던 문제들 중에 가장 시뮬 성향이 강했던 문제라 제일 먼저 풀 수 있었다. 왼쪽부터 시작하는 인덱스 포인터랑 오른쪽부터 시작하는 인덱스 포인터를 관리하면서, 반복문을 돌아주면 된다.
public class probD {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
for (int t=1; t<=T; t++) {
int N = Integer.parseInt(bf.readLine());
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int[] candy = new int[N];
for (int i=0; i<N; i++) {
candy[i] = Integer.parseInt(st.nextToken());
}
int candy_a = 0;
int candy_b = 0;
int next_min_candy = 0;
int thisturn_a = 0;
int thisturn_b = 0;
int index_a = 0;
int index_b = N-1;
int moves = 0;
while (true) {
while(thisturn_a <= next_min_candy) {
thisturn_a += candy[index_a++];
if (index_a > index_b)
break;
}
moves++;
candy_a += thisturn_a;
next_min_candy = thisturn_a;
if (index_a > index_b)
break;
while(thisturn_b <= next_min_candy) {
thisturn_b += candy[index_b--];
if (index_b < index_a)
break;
}
moves++;
candy_b += thisturn_b;
next_min_candy = thisturn_b;
thisturn_a = 0;
thisturn_b = 0;
if (index_a > index_b)
break;
}
System.out.print(moves + " " + candy_a + " " + candy_b + "\n");
}
}
}
E. Special Elements
양수들이 들어있는 배열이 주어지는데, 배열의 원소 중 "L~R번째까지의 연속된 원소들의 합" 으로 표현가능한 원소를 Special Element라고 한다.
예를 들어 [3, 1, 4, 1, 6] 가 주어졌을 때 4는 1~2번째 원소의 합으로 표현가능하고, 6은 2~4번째 원소의 합으로 표현가능하므로 Special Element이다. 문제는 주어진 배열에서 Special Element의 개수를 구하는 것이다.
일단 문제에 써있는 그대로 구현을 해보려고 했다. 각 원소마다 스페셜인지 체크하기 위한 for문, 그리고 그 안에서 가능한 모든 L~R의 조합을 해보면서 합을 구하는 for, for, for... 아름다운 4중 for문이 완성되었고 당연히 시간초과가 났다.
다음으로 생각한 방법은 L~R의 합이라는 게 중복으로 나올 수도 있으니까 Set을 사용해서 중복을 제거해준 다음 다 끝나고 set.contains() 로 찾자는 것이었다. 4중 for문이 3중으로 줄긴 했지만 여전히 시간초과가 났다.
여기까지 하고 다른 문제로 넘어갔고 결국 시간 내에 풀지 못했다.
L~R을 더하는 과정에서 중복이 너무 많이 발생한다는 느낌 정도는 가지고 있었지만 아이디어가 떠오르지 않았는데, 대회가 끝나고 나서 좀 더 붙잡고 있다보니 DP로 풀 수 있는 방법이 생각이 났다.
R이 커질 때마다 매번 L~R을 더하고 있는게 아니라, 이전까지 구했던 합을 배열에 저장하고 거기다가 R번째 원소에 해당하는 값만 더하는 것이다.
다만 문제의 메모리 제한이 빡빡했기 때문에 2차원 배열로 만들었더니 메모리 초과가 났다. 생각해보면 어차피 합은 따로 Set에 저장하니까 DP 배열을 나중에 다시 쓰진 않으니 1차원 배열만 만들어두고 재사용해도 상관없었다.
거기에 추가로 처음에 입력을 받을 때 배열 원소들 중 최대값을 저장해뒀다가, 합을 계산하는 도중에 최대값을 넘어가버리면 거기서 break하도록 가지치기를 더 했다.
public class probE {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
for (int t=1; t<=T; t++) {
int N = Integer.parseInt(bf.readLine());
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int[] arr = new int[N];
int[] dp_arr = new int[N];
TreeSet<Integer> s = new TreeSet<Integer>();
int max = 0;
for (int i=0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
if (arr[i] > max)
max = arr[i];
}
for (int l=0; l<N-1; l++) {
dp_arr[l] = arr[l];
for (int r=l+1; r<N; r++) {
int sum = dp_arr[r-1] + arr[r];
if (sum > max)
break;
dp_arr[r] = sum;
s.add(sum);
}
}
int count = 0;
for (int i=0; i<N; i++) {
if (s.contains(arr[i]))
count++;
}
System.out.println(count);
}
}
}
이렇게 비록 대회 시간 내에는 못 풀었지만 어떻게든 통과... 한 줄 알았는데...
이 포스팅을 쓰는 도중에 Hack 당했다는 알림이 떴다. 이 Hack이라는게 뭐냐면... 코드포스에선 대회 시작 후 한동안은 코드를 제출하면 적은 양의 테스트 케이스로만 채점을 해서 통과 여부를 알려준다. 그리고 나중에, 시간이 흐른 뒤에 제대로 된 TC로 채점한 결과를 알려주는데, 그 사이에 다른 사람이 제출한 코드에 TC를 넣어서 Hacking할 수 있는 시간이 주어진다. 즉 Hack 당했다는 말은 처음에 주어지는 적은 양의 TC로는 통과한 것처럼 보였지만 사실은 틀렸다는 의미다... 풀었다고 좋아했는데 얼마 되지도 않아서 빨간색으로 Hacked라 뜨는걸 보니까 기분이 씁쓸하더라.
F. Binary String Reconstruction
'0001101' 과 같은 Binary String이 있다. 연속된 2개의 숫자가 '00' 인 쌍의 개수를 a, '01' 이나 '10' 인 쌍의 개수를 b, '11' 인 쌍의 개수를 c라 하자. 예를 들어 '0001101' 의 경우 00, 00, 01, 11, 10, 01로 쪼개볼 수 있고 a=2, b=3, c=1이다.
입력으로 a, b, c가 주어지면 그 조건을 만족하는 Binary String을 아무거나 만들어내면 되는 문제이다.
처음에는 그냥 Greedy 느낌으로 적당히 만들어주면 될 것 같은 느낌을 받았지만 좀처럼 코드가 떠오르지 않았고... 그러다가 재귀를 이용한 해법을 생각해냈다.
빈 String으로 시작해서 재귀를 이용해서 숫자를 하나씩 붙여주는데, a, b, c가 남아있는지 여부에 따라 조건을 줘서 재귀를 태우는 것이다. 그러니까 현재 String의 끝자리가 0인 경우엔 a가 남아있으면 0을 하나 더 붙여보고, b가 남아있으면 1을 하나 더 붙여보는 식이다.
그럴듯하다고 생각했지만 시간초과가 났다. 이게 아닌가 싶어서 Greedy하게 풀어보려고도 시도했는데 그것도 잘 안돼서 결국 시간 내엔 풀지 못했다. (나중에 올라온 풀이를 살짝 보니까 Greedy로도 충분히 풀 수 있는 문제였다)
끝나고 나서야 중요한 가지치기 조건을 빼먹었다는 것을 깨달았다. 조건을 만족하는 Binary String 중 아무거나 출력하면 되기 때문에, 조건을 만족하는 재귀의 끝에 한 번만 도달하고 나면 그 다음부턴 다 필요없고 그냥 끝내면 되는 것이었다... 이걸 붙여주니 풀렸다. 대회 끝나자마자 바로 발견해서 좀 아쉬웠다. 이것까지 3문제 풀었다면 그래도 나름 만족스러웠을텐데...
public class probF {
static int length;
static String ans;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
for (int t=1; t<=T; t++) {
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
length = a+b+c;
ans = "";
dfs("0", a, b, c, 1);
dfs("1", a, b, c, 1);
System.out.println(ans);
}
}
private static void dfs(String str, int a, int b, int c, int depth) {
if (!ans.equals("")) {
return;
}
if (depth > length+1) {
return;
}
if (a > 0 && c > 0 && b == 0)
return;
if (a == 0 && b == 0 && c == 0 && depth == length+1) {
ans = str;
return;
}
char last = str.charAt(str.length()-1);
if (last == '0') {
if (a > 0) {
dfs(str+"0", a-1, b, c, depth+1);
}
if (b > 0) {
dfs(str+"1", a, b-1, c, depth+1);
}
}
else if (last == '1') {
if (b > 0) {
dfs(str+"0", a, b-1, c, depth+1);
}
if (c > 0) {
dfs(str+"1", a, b, c-1, depth+1);
}
}
}
}
G. Special Permutation
1~N까지로 구성된 순열을 만드는데, 각 이웃한 수끼리의 차이가 2~4여야 한다는 조건을 만족하는 순열을 만드는 문제. N이 최대 1000이기 때문에 완탐으로는 당연히 안되고... 다른 문제 보다가 이미 시간도 다 써서 그냥 포기했다.
코드포스에선 대회가 끝나면 Editorial이라고 해서 간략한 문제 풀이가 올라온다. 다 읽어보기는 귀찮아서 다 보진 못했는데 역시 B, C같은 경우는 수학 머리가 좀 필요한 거였고 F는 생각보다 더 쉽게 Greedy로 풀리는 문제였다...
여튼 내가 얼마나 부족한지 다시 한번 느낄 수 있는 경험이었고 조금은 더 다양한 문제를 접해볼 필요도 있을 것 같다. 물론 ICPC같은 대회 준비하는 것도 아니니 그렇게까지 막 이런 쪽에 매달릴 필요도 없겠지만...