본문 바로가기

PS

Google Code Jam 2020 Round 1A 후기

잠수탄다는 네모 어디

많이 바쁘긴 한데 학기 중 대회 즐기는 걸 생각하면서 겨울방학에 그렇게 공부햇는데 안 치는 게 말이 안된다.

결과도 꽤 만족스럽게 나와서 후기 써야지!

 

코딩할 줄 알고 (Pattern Matching) / 파스칼 삼각형 들어봤고 비트연산 할 줄 알면 (Pascal Walk) 두 문제를 풀 수 있다. 마지막 문제를 잡을 때는 시간이 조금 남았는데 지문 읽으면 끝날 거 같아서 과제하러 튀었다. 킥스타트랑 다르게 구코잼은 더 큰(?) 대회인만큼 비전형적인 문제가 많다. 그래도 1라운드까지는 알고리즘을 쓰는 문제는 잘 안 나온다. 

 

 

# Pattern Matching

 

[문제]

a*b*c, a*b*, 이런식으로 여러 개의 문자열이 원본 문자열의 일부를 *으로 치환한 채로 주어진다. 원본 문자열을 찾을 수 있는가? 찾을 수 있다면 무엇인가.

 

[풀이]

*에 어떤 것이든 들어올 수 있다는 것이 키포인트이다. 첫번째 별 앞에 있는 문자열이랑 마지막 별 뒤에 있는 문자열만 적당히 처리한다. 그 다음에는 별 사이사이에 있는 문자열은 적당히 아무 순서대로 이어붙이면 된다.

 

[여담]

문자열 보고 뇌정지와서 튀었는데, B 풀고 돌아와서 다시 읽으니 짱쉽......... 덕분에 시간 패널티를 많이 먹었다 ㅠㅠ


# Pascal Walk

 

[문제]

파스칼삼각형의 1행 1렬에서 시작해서 경로를 따라 걸어가자. 가는 길에 있는 수를 다 합쳤을 때 n이 될 수 있는 적당한 경로를 찾을 수 있는가? 찾을 수 있다면 무엇인가. (경로는 같은 칸을 또 포함할 수 없으며, 인접해있어야 한다.)

 

[풀이]

파스칼 삼각형 한 행을 다 가져다 더하면 2^n이 된다는 사실을 알면 N을 구성하는 비트에 해당되는 행들을 싹 더하고 싶다는 강한 충동이 든다. 문제는 각 행들을 경로로 이어주어야 한다는 사실이다.

 

이전 행과의 이번 행의 거리를 k라고 하자. k가 1인 경우, 2인 경우, 3 이상인 경우로 나누어 구현하자.

여기서 핵심은, 내려오는 과정에서 k "이상" 만큼 덜 더하게 만들어야 하는 사실이다. 그럼 나중에 sum<=n이 될텐데, 부족한만큼은 쭉 1을 따라 내려가면 된다. 

 

거리가 1인 경우에는 이전 행을 쭉 훑고 그냥 바로 내려와서 반대방향으로 이번 행을 훑는다.

거리가 2인 경우에는 이번 행의 1열을 건너뛰고 2열부터 훑자.

 

거리가 3이상인 경우는, 크리스마스 양말 정리(=하키스틱 정리)를 알고 있으면 발상하기 편하다. 몰라도 되긴 된다.

적당히 내려오다가 2전행의 두 번째 열, 직전행의 세 번째 열을 밟고, 이번 행은 4번째 열부터 훑어주면 된다. 이 경우 언제나 k 이상 아껴줄 수 있는데, 직접 그려보고 이해하자. (과제하느라 바쁘다.............방학에 추가해야지)

 

꿀팁으로, 방향 생각하기 귀찮은데 이런 함수 하나 짜두면 많이 편해진다.

1
2
3
4
int f(int dir, int a, int b){
    if(dir==1return b;
    else return a+1-b;
}
cs

 

왜 500번 이하로 해결가능한 지 보이는 법을 간단히 설명하자면, 여분의 1이 발생하는 게 거리가 3 이상인 경우가 제일 크리티컬하다. 그런데 거리가 3인 경우는 많아봐야 10개 정도만 존재하는데(n의범위가 2^30이하이기 때문에) 위에서 언급한 방식으로 구현했을 때 발생하는 1의 개수의 상한을 대강 계산해보고, 여기에 행 긁어주는 거 더해봤자 500 이하이다. 자세한 건 직접 해보자! 제한이 널널하기 때문에 계산 열심히(?) 안해도 된다. 나중에 추가해야지 22


마지막 문제를 잡는 시점에서는 시간이 30분밖에 남지 않았고, 문제 읽으면 끝날 것 같아서 기도메타 타고 과제하러 갔다. 사실 튀었을 때 2700여등이었기에 1B나 1C 칠 생각을 하고 있었는데, 부분점수 긁는 사람들이 생각보다 많았는지, 등수 반토막 나있어서 놀랐다.

 

작년엔 1C에서 광탈했었기 때문에, 많이 쫄려있었는데, 1A로 통과해서 기분이 좋다 ㅎㅅㅎ !

'PS' 카테고리의 다른 글

BOJ#18865 이제 다시 시작이다  (0) 2020.07.11
ICPC 2017 인터넷 예선 업솔빙 후기  (0) 2020.07.01
Kick Start Round A 2020 후기  (0) 2020.03.23
BOJ#11993 Circular Barn (Gold)  (0) 2020.03.10
USACO 2016 February Gold 업솔빙  (0) 2020.03.09