제가 속했던 팀(the pulza)가 안드로메다로 여행을 떠난 이유 중 하나는 바로 이문제 때문이 아니었을까 싶습니다(실제로도 대회에서는 풀지 못했고, 대회가 끝나고 알고스팟의 중계를 보고 난 직후에야 풀게 되었던 문제입니다.)
하지만 statistics를 봤을 경우 참가한 팀 중에서 21팀이 풀었던 문제인지라 난이도는 그리 어렵지 않다라고 평가를 할 수 있을듯 합니다.
처음에 봤을 때 ICPC계에서 조금이라도 발을 붙이신 분이라면 떠올랐을 문제가 있을 겁니다.
혹시 이 문제를 풀지 못하셨던 분이라면 먼저 추천해드리고 싶은 문제가 있습니다. 아직도 푸시지 못하신 분은 이 문제 부터 풀어보시길 바랍니다.
Tiling : http://acm.pku.edu.cn/JudgeOnline/problem?id=2506
위의 문제는 동적계획법으로 풀 수 있으며, 이 문제를 풀기 위한 점화식은 다음과 같습니다.
D[N] : N길이의 모든 가지수
D[N] = D[N-1] + D[N-2] * 2[/spoiler]
E번 문제 역시 동적계획법 문제이지만, 차이점이 있습니다. 그것이 무엇인지 지금부터 설명을 하고자 합니다.
E번 문제가 까다로왔던 이유는 다름이 아니라, 다음과 같은 그림이 동일한 경우인 한가지로 체크가 되기 때문입니다(좌우로 뒤집었을 경우 서로 동일한 모양이 나올 경우)
A : 문제에서 요구한 조건을 고려하지 않은 모든 가지수 - 이는 Tiling 문제를 풀때 처럼 구하면 됩니다.
B : 대칭을 이루는 모양의 가지수
C : 좌우로 뒤집었을 경우의 동일한 모양이 나오는 경우의 수
D : 문제에서 요구하는 답
C = (A-B) / 2
D = C + B
마지막으로 남은 것은 대칭을 이루는 모양의 가지수 인데요. 길이 N에 대해서 대칭을 이루는 경우의 수는 다음과 같이 구합니다(여기서 문제 조건을 고려하지않은 길이 N에 대한 모든 경우는 P[N]으로 표기합니다.)
우선 길이가 홀수 일경우엔 1 x 2 타일이 가운데에 세워져 있는 모양일 경우를 기준으로 대칭이 되기 때문에 P[(N-1)/2] 가 대칭을 이루는 경우가 됩니다.
짝수의 경우엔 절반의 모양이 대칭이 되는경우와, 1 x 2 타일이 2개가 눕혀진 모양으로 2 x 2 크기로 가운데에 존재하는 경우 혹은 2 x 2 타일이 가운데에 위치한 경우가 존재하므로 가지수는 P[N/2] + 2 * P[(N-2)/2]가 됩니다.
이것만 해결하면 아래와 같이 간결한 소스코드가 나오게 됩니다. 대회에서 못푼 문제라는 점이 아쉽긴 하지만, 꽤나 재미있는 문제 중에 하나가 아니었나 싶습니다.
#include <iostream>usingnamespacestd;typedeflonglongll;llp[31];// 문제 조건을 고려하지 않은 가지수를 저장한 테이블lld[31];// N에 대한 답을 저장하는 테이블 voidprepare(){p[1]=1;p[2]=3;for(inti=3;i<=30;++i)p[i]=p[i-1]+p[i-2]*2;d[1]=1;d[2]=3;for(inti=3;i<=30;++i){llB;if(i%2==1){B=p[(i-1)/2];}else{B=p[i/2]+2*p[(i-2)/2];}d[i]=(p[i]-B)/2+B;}}intmain(){prepare();intT,N;cin>>T;while(T--){cin>>N;cout<<d[N]<<endl;}}
hyunhwan
제가 속했던 팀(the pulza)가 안드로메다로 여행을 떠난 이유 중 하나는 바로 이문제 때문이 아니었을까 싶습니다(실제로도 대회에서는 풀지 못했고, 대회가 끝나고 알고스팟의 중계를 보고 난 직후에야 풀게 되었던 문제입니다.)
하지만 statistics를 봤을 경우 참가한 팀 중에서 21팀이 풀었던 문제인지라 난이도는 그리 어렵지 않다라고 평가를 할 수 있을듯 합니다.
처음에 봤을 때 ICPC계에서 조금이라도 발을 붙이신 분이라면 떠올랐을 문제가 있을 겁니다.
혹시 이 문제를 풀지 못하셨던 분이라면 먼저 추천해드리고 싶은 문제가 있습니다. 아직도 푸시지 못하신 분은 이 문제 부터 풀어보시길 바랍니다.
Tiling : http://acm.pku.edu.cn/JudgeOnline/problem?id=2506
위의 문제는 동적계획법으로 풀 수 있으며, 이 문제를 풀기 위한 점화식은 다음과 같습니다.
D[N] : N길이의 모든 가지수
D[N] = D[N-1] + D[N-2] * 2[/spoiler]
E번 문제 역시 동적계획법 문제이지만, 차이점이 있습니다. 그것이 무엇인지 지금부터 설명을 하고자 합니다.
E번 문제가 까다로왔던 이유는 다름이 아니라, 다음과 같은 그림이 동일한 경우인 한가지로 체크가 되기 때문입니다(좌우로 뒤집었을 경우 서로 동일한 모양이 나올 경우)
A : 문제에서 요구한 조건을 고려하지 않은 모든 가지수 - 이는 Tiling 문제를 풀때 처럼 구하면 됩니다.
B : 대칭을 이루는 모양의 가지수
C : 좌우로 뒤집었을 경우의 동일한 모양이 나오는 경우의 수
D : 문제에서 요구하는 답
C = (A-B) / 2
D = C + B
마지막으로 남은 것은 대칭을 이루는 모양의 가지수 인데요. 길이 N에 대해서 대칭을 이루는 경우의 수는 다음과 같이 구합니다(여기서 문제 조건을 고려하지않은 길이 N에 대한 모든 경우는 P[N]으로 표기합니다.)
우선 길이가 홀수 일경우엔 1 x 2 타일이 가운데에 세워져 있는 모양일 경우를 기준으로 대칭이 되기 때문에 P[(N-1)/2] 가 대칭을 이루는 경우가 됩니다.
짝수의 경우엔 절반의 모양이 대칭이 되는경우와, 1 x 2 타일이 2개가 눕혀진 모양으로 2 x 2 크기로 가운데에 존재하는 경우 혹은 2 x 2 타일이 가운데에 위치한 경우가 존재하므로 가지수는 P[N/2] + 2 * P[(N-2)/2]가 됩니다.
이것만 해결하면 아래와 같이 간결한 소스코드가 나오게 됩니다. 대회에서 못푼 문제라는 점이 아쉽긴 하지만, 꽤나 재미있는 문제 중에 하나가 아니었나 싶습니다.
16년 전