Asia - Jakarta - 2008/2009 - Problem B: Bonus Treasure
문제는: http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4139
앞으로 ACM-ICPC 지역 예선에서 1~2문제는 쉽게 풀 수 있는데, 3~5문제를 풀 수 있으려면 어떤 공부를 해야 할까? 라는 것에 집중하고자 합니다.
그런 의미에서 각 대회에서 가장 어려웠던 문제들과 가장 쉬웠던 문제들을 제외한 나머지 문제를 다루겠습니다.
문제 B는 전체 49팀중 16팀이 푼 문제입니다. 문제 A는 17팀이 풀었으니 실제 난이도는 비슷하다고 할 수도 있겠습니다.
(그래도 A가 B보다 좀 더 어려운 것 같은 기분이 듭니다)
이 문제는 N번째 master sequence S(N)의 K번째 문자부터 이어지는 M개의 문자들을 출력하는 문제입니다.
S(N)은 괄호를 열고 S(0)부터 S(N-1)을 나열한 다음, 괄호를 닫은 문자열로 정의됩니다.
S(N)을 생성한 다음에 K번째 문자부터 M개를 읽어서 출력하면 되지 않겠는가? 라고 생각할 수 있지만, S(N)의 길이는
S(1) 의 길이가 2
S(2) 의 길이가 2+2 = 4
S(3) 의 길이가 2+4+2 = 8
S(4) 의 길이가 2+4+8+2 = 16
S(5) 의 길이가 2+4+8+16+2 = 32
S(6) 의 길이가 2+4+8+16+32+2 = 64
식으로 S(N-1)의 길이 * 2 + 2 이고, N은 최대 31이기 때문에,
S(N)의 길이는 2^N 을 넘게 됩니다. 2^31 byte이면 약 2^21 KB, 2^11 MB, 2GB 정도이므로 다음과 같이 실제로 S(N)을 생성하는 코드를 실행시키면 도저히 시간제한 안에는 돌아가지 않을 것 같아 보입니다.
다행히도 S(N)은 비슷한 형태가 반복되는 형태임을 이용해서 접근해 봅시다.
예를 들어, S(4) 은 ( ( ) ( ( ) ) ( ( ) ( ( ) ) ) ) 인데요, 이것은 "(" + S(1) + S(2) + S(3) ")" 이면서,
S(3)-")" + S(3)-")" + ")" 이기도 합니다. ( ( ) ( ( ) ) ( ( ) ( ( ) ) ) )
이를 이용해서 원하는 string의 시작위치, 끝나는 위치, M+K가 S(N)의 마지막 닫는 괄호를 포함하는가? 를 case by case 처리하는 답 프로그램을 만들어 볼 수 있습니다.
S(N) 의 구조를 S(N-1)-")" + S(N-1)-")" + ")" 으로 파악한다면
M+K가 2^N과 같은 경우를 약간 다르게 처리해 주면 됩니다.
사실 정석대로(?) 라면 "(" + S(1) + S(2) + S(3) + ... ")" 구조에 따라 M번째 문자까지 나오는 (, S(1), S(2)... 등을 생략하고 K개를 추가해야 겠지만, 코딩하다가 말려서... 설명한 대로 짜봤습니다..;
소스보기
문제는: http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4139
앞으로 ACM-ICPC 지역 예선에서 1~2문제는 쉽게 풀 수 있는데, 3~5문제를 풀 수 있으려면 어떤 공부를 해야 할까? 라는 것에 집중하고자 합니다.
그런 의미에서 각 대회에서 가장 어려웠던 문제들과 가장 쉬웠던 문제들을 제외한 나머지 문제를 다루겠습니다.
문제 B는 전체 49팀중 16팀이 푼 문제입니다. 문제 A는 17팀이 풀었으니 실제 난이도는 비슷하다고 할 수도 있겠습니다.
(그래도 A가 B보다 좀 더 어려운 것 같은 기분이 듭니다)
이 문제는 N번째 master sequence S(N)의 K번째 문자부터 이어지는 M개의 문자들을 출력하는 문제입니다.
S(N)은 괄호를 열고 S(0)부터 S(N-1)을 나열한 다음, 괄호를 닫은 문자열로 정의됩니다.
S(N)을 생성한 다음에 K번째 문자부터 M개를 읽어서 출력하면 되지 않겠는가? 라고 생각할 수 있지만, S(N)의 길이는
S(1) 의 길이가 2
S(2) 의 길이가 2+2 = 4
S(3) 의 길이가 2+4+2 = 8
S(4) 의 길이가 2+4+8+2 = 16
S(5) 의 길이가 2+4+8+16+2 = 32
S(6) 의 길이가 2+4+8+16+32+2 = 64
식으로 S(N-1)의 길이 * 2 + 2 이고, N은 최대 31이기 때문에,
S(N)의 길이는 2^N 을 넘게 됩니다. 2^31 byte이면 약 2^21 KB, 2^11 MB, 2GB 정도이므로 다음과 같이 실제로 S(N)을 생성하는 코드를 실행시키면 도저히 시간제한 안에는 돌아가지 않을 것 같아 보입니다.
#include <iostream>
#include <string>
using namespace std;
string generateS(int N) {
if (N == 1) return string("()");
string S("(");
for(int i=0; i<N; i++) {
S += generateS(i);
}
S += ")";
return S;
}
int main() {
generateS(32);
return 0;
}
다행히도 S(N)은 비슷한 형태가 반복되는 형태임을 이용해서 접근해 봅시다.
예를 들어, S(4) 은 ( ( ) ( ( ) ) ( ( ) ( ( ) ) ) ) 인데요, 이것은 "(" + S(1) + S(2) + S(3) ")" 이면서,
S(3)-")" + S(3)-")" + ")" 이기도 합니다. ( ( ) ( ( ) ) ( ( ) ( ( ) ) ) )
이를 이용해서 원하는 string의 시작위치, 끝나는 위치, M+K가 S(N)의 마지막 닫는 괄호를 포함하는가? 를 case by case 처리하는 답 프로그램을 만들어 볼 수 있습니다.
S(N) 의 구조를 S(N-1)-")" + S(N-1)-")" + ")" 으로 파악한다면
- M이 2^(N-1)-1보다 작고, M+K또한 2^(N-1)-1보다 작다면, S(N, M, K) - S(N)에서 M번째 문자부터 K개의 문자 - 는 S(N-1, M, K)와 같습니다.
- M이 2^(N-1)-1보다 작지만, M+K가 2^(N-1)-1보다 크다면, S(N, M, K)는 S(N-1, M, 2^(N-1)-1-M) 과 S(N-1, 0, M+K-2^(N-1)+1 )와 같습니다.
- M이 2^(N-1)-1 보다 크면, S(N, M, K)는 S(N-1, M-2^(N-1)+1, K) 와 같습니다.
M+K가 2^N과 같은 경우를 약간 다르게 처리해 주면 됩니다.
사실 정석대로(?) 라면 "(" + S(1) + S(2) + S(3) + ... ")" 구조에 따라 M번째 문자까지 나오는 (, S(1), S(2)... 등을 생략하고 K개를 추가해야 겠지만, 코딩하다가 말려서... 설명한 대로 짜봤습니다..;
소스보기










덧글
JM 2009/05/26 00:59 # 삭제 답글
효율성은 좀 떨어지더라도, 'k번째 글자부터 m글자의 구간' 을 반환하는 함수가 아니라 'k번째 글자' 를 반환하는 함수를 짜면 코딩이 쉬워지는 일이 심심찮게 있습니다.char charAt(unsigned n, unsigned k)
{
if(n == 1) return (k == 0 ? '(' : ')');
if(k == 0) return '(';
--k;
for(unsigned i = 1; i < n; ++i)
if(k >= (1u << i))
k -= (1u << i);
else
return charAt(i, k);
return ')';
}
그리고 m번 호출해서 문제를 해결하는 것이죠. ^^;
Josh 2009/06/03 23:27 # 답글
이런 글 찾아 읽기보다는 <cond> ? <value> : <value> 표현이라던가 라던가 << >> (shift 연산) 같이 사용할 언어의 feature들을 완벽히 파악하는 게 더 필요할지도 모르겠네요.