back to 2021

(! 260518 13:11 오타 수정)

 

잠이 안 오는 새벽 세 시 반이다. 정수론 과제 소문제 하나에 1시간 반을 매달렸지만 결국 반쯤 이해한 채로 gpt의 풀이를 베껴서 내고, 인간관계에 대한 깊생도 들고, 해석학 시험은 얼마 남지 않았고, 최근 교내 ps대회도 말아먹고서 생각이 많아진 그런 날이라고 할까.

 

침대에서 뒹굴거리며 핸드폰을 들여다봤고, 2020년부터 사용했던 내 트위터 계정을 구경하며 나름의 추억팔이를 하다 '학교에서 수행평가로 나왔던 확통 문제인데 어떻게 푸는지 잘 모르겠다'는 내 질문글을 보게 되었다. 필자는 인과영 확통 내신에서 B-(석차로 따지면 9등급제 기준 8등급 정도)를 받았다. 중학교 2학년 때 잠시 중등 KMO를 준비할 때도 조합론 문제는 단 한 개도 맞추지 못했다. 조합론은 근사(not approximation yes cool)하고 재밌지만 묘하게 재능을 타며, 아쉽게도 나에게는 그 재능이 없다.

 

당시 설컴을 다니고 경곽 같은 데 다니던 멋진 트친 분들이 답장을 해 주신 걸 구경하는데 꽤나 흥미로웠다. 근데 읽다가 되게 많이 나오는 DP 문제 아님? 이라는 생각이 들었다. 그래서 풀어봤는데 이게 맞네?

 

이하 풀이:

일단 문제가 대칭적이기 때문에 첫 번째를 1로 고정하고 나중에 4를 곱할 것이다. i번째에 고른 수가 처음에 고정한 수와..

A[i]: 같은 경우 (ex. 1)

B[i]: 반대인 경우 (ex. -1)

C[i]: 상관없는 경우 (ex. i, -i) 

 

그러면 점화식을 세울 수 있는데 

A[i+1] = A[i]+C[i]

B[i+1] = B[i]+C[i]

C[i+1] = 2*A[i]+2*B[i]+C[i]

초깃값은 A[0]=1, B[0]=C[0]=0이다.

 

마지막도 반대이면 안 된다. 따라서 4*(A[n-1]+C[n-1])이 답이 된다.

 

여기에 식을 구하고 싶다면 A[i]+B[i]+C[i]=3^i (임의의 순간에 길이 i+1의 sequence를 만드는 방법은 직전 꺼를 제외한 나머지 3개이고 시작은 3^0=1이다)을 이용해서 식정리를 해주면 된다. 점화식을 풀면 길이 n에 대해 3^n+(-1)^n+2 라는 closed form을 얻을 수 있다. 악필이라 ㅈㅅ

 

당시 학교에서 배웠던 조금 더 고능한 조합론적 풀이도 첨부했다. 

 

고등학생 때의 내가 못 풀어서 결국 풀이를 외워버렸던 확통 문제를, 대학생이 되어 알고리즘 문제풀이를 시작하고 DP 문제로 바꿔서 풀어냈다는 점에서 스스로의 발전이 뿌듯하게 느껴졌다. ps가 절대적인 발상력을 높여주는 건 아니지만 가능한 발상의 폭을 넓혀주긴 하는 것 같다. 대학교 와서 뭘 했지? 라는 생각을 아주 많이 했지만, 사실은 나도 모르게 조금씩 성장했을지도 모른다. (ㅈㅅ 제가 씹덕이라 성장, 결실 같은 키워드에 환장함)

 

+ LLM에게 풀이의 유효성을 검증받았더니 4-state graph에서 길이 n의 walk를 계산하는 문제로 환원할 수 있다고 해서 신기했다. 뭔진 잘 모르겠지만 만약 알고리즘에 대한 내 관심이 계속된다면 그래프의 성질도 공부해보면 재밌을 것 같다. (뭐든 쉽게 질리는 성격 탓에 그럴진 모르겠긴 함)

+ 백준에 동일한 문제가 있을까? 하고 검색해보려고 했는데 아 백준이 없어졌구나... 라는 걸 깨달았다. 주변인들에게 물어봤더니 실버~골드하위 DP이고 식까지 구하는 건 골드 상위~플레 하위라는데 그럼 난 실버랑 골드를 풀고 신나서 블로그 글을 쓴 거구나(!) 좀 부끄러워졌을지도?

 

+ mathtw1030님이 알려주셨다! 이게 있네?