제2회 곰곰컵 회고

제2회 곰곰컵은 알고리즘 빡공방에서 정체를 알게 되었다.

뱃지와 배경화면을 준다길래 열심히 풀었다.

 

대회에서 푼 문제

551명 중 101등을 했다.

문제는 출제진이 알려준 것처럼 어렵지 않게 느껴졌다.

1개를 풀면 곰곰 했어요를, 7개를 풀면 곰곰 잘했어요를 받는다.

본인은 5개밖에 풀지 못해서 아쉽게도 하나만 받았다. ㅠㅠ

곰곰 했어요

곰곰 잘했어요

혼자 풀어본 문제

많은 시간을 들여가며 K번째 문제까지 풀었다. (이후 문제는 플레티넘 난이도지만 복잡도가 높아 풀지 않았다)

이번 문제는 에드혹 문제, 함정 문제가 많았다.

애디토리얼

https://upload.acmicpc.net/241319de-a09a-41ad-aad9-360e3cbbc391/

 

🧩 F. 외로운 곰곰이는 친구가 있어요

예시 입력의 세번째 친구를 보면 3, 9 칸씩 움직일 수 있는데, 좀 복잡하게 6, 9이라고 하자.

6, 9을 움직일 수 있다면 결국 3칸 단위로 움직인다는 말이 된다.

왜 그럴까?

 

x를 6칸 움직인 수, y를 9칸 움직인 수로 하면 $6x + 9y = 10$와 같다.

그런데, $ax + by  = d$는 $gcd(a, b) = d$로 표현할 수 있다.

그러니까 $gcd(a, b) = d$ 일때 ax + by  = d로 표현할 수 있다. (이걸 배주 항등식이라고 한다고 함)

이 식은 아래 글에서 다룬 적이 있다.

https://2jun0.tistory.com/69

 

따라서 $6x + 9y = gcd(6, 9)*k = 10 (k는 정수)$ 가 만족해야 한다. 3*k이라서 만족 못한다.

 

🧩 G. 곰곰이와 테트리스

게임이론 문제로, 골때리는 문제다.

예전에 카카오 코테 문제로 아주 비슷한 것을 푼 적이 있다.

승자는 계속 이기는 수를 두고, 패자도 가능한 한 최선의 수를 두는데 결국엔 승자 패자가 있다는 문제다.

 

이런 문제는 많이 풀어보지 않아서 너무 어려웠다.

 

하지만 알고보니 쉽게 푸는 방법이 있었다.

곰곰이가 먼저 가운데에 두면 이긴다는 것이다. (가운데에 둘 수 없는 1x2격자의 경우 지게 된다)

 

🧩 H. 곰곰아 선 넘지마

이 문제도 어려웠다.

핵심은 S와 T의 1을 같은 위치에 두려면 T든 S든 i번째 1의 위치를 같게 해야 한다는 점이였다.

 

풀이는 복잡해서 에디토리얼 보는게 좋을 것 같다.

 

🧩 I. 곰곰이의 식단 관리 2

bfs를 알면 잘 풀수 있기는 개뿔 엄청 어렵다

bfs+에드혹 문제였다..

 

🧩 J. 서커스 나이트

에라토스테네스 킹갓짱선생님의 체를 빌려와서 소수를 구한 뒤, 소인수 분해를 하면 쉽게 풀 수 있다.

 

소인수 분해를 한 뒤, 소인수와 숫자들에 대해서 방문 처리를 하면서 bfs를 돌리면 끝!

풀이 없이 풀었다.

 

🧩 K. 곰곰이와 토너먼트

음.. 여기선 갑자기 수능 공부를 하는 느낌이 들었다.

조합론을 이용해 경우의 수를 구하는 문제였다.

 

종종 이렇게 조합 문제가 나와서 한번 풀어 보았다.

 

💬 느낀점

이번 대회는 수학 풀이능력과 풀이 센스가 요구되는 문제가 많았던 것 같다.

그래서 더 어려운 느낌이 들었고, 플레 이상의 자료구조를 쓰지 않은 최고의 문제들을 풀었던 것 같다.

 

아쉽게도 뱃지는 다 받지 못했지만 문제가 재밌어서 오랫동안 물고 뜯을 수 있었다.

그리고 곰곰이 귀엽다