Codeforces Round 946 (Div. 3)

간만에 Div.3를 쳤는데 첫 민트 퍼포먼스가 떠서 글을 작성해본다.

 

민트 퍼포먼스가 뜬거지 민트가 된건 아니다...

 

Div 3, 4만 열심히 치다보면 블루에 가는 날이 올 수도??

 

무슨 문제가 나왔는지 살펴보자.

 

A. https://codeforces.com/contest/1974/problem/A

Problem - A - Codeforces

5x3 화면 안에 1x1과 2x2 크기의 앱들을 넣으려면 몇 개의 화면이 필요한지 묻는 문제다.

브르투포스로 카운트 했다. A번 답게 쉬운 문제

 

정답 코드 : https://codeforces.com/contest/1974/submission/261799934

 

B. https://codeforces.com/contest/1974/problem/B

Problem - B - Codeforces

문자열이 주어지고 그 문자열에 포함된 단어들을 한번씩만 사용해서 오름차순으로 정렬한 문자열을 새로 만든다.

기존의 문자열을 S, 새로 만든 문자열을 R이라 하자.

 

기존의 문자열을 출력하는데

문자열 R의 idx번째에 있는 문자를 (R의 길이) - 1 - idx에 위치하는 문자(팰린드롬)로 바꿔서 출력한다.

이미 한 번 위의 과정이 수행된 문자열이 주어지고 다시 위의 과정을 반복해서 출력하면 답이다.

 

간단한 팰린드롬 문제였는데 (R의 길이) - 1 - idx를 n(S의 길이) - 1 - idx로 뒀다가 왜 안되지 하면서 뇌정지가 왔었다.

 

정답 코드 : https://codeforces.com/contest/1974/submission/261828041

 

C. https://codeforces.com/contest/1974/problem/C

Problem - C - Codeforces

정수 배열에서 인접한 3개씩 묶은 값을 x, y, z라 할 때 다른 x, y, z와 자리별로 비교해서 같은 값 2개, 다른 값 1개가 몇 개인지 묻는 문제다.

 

인공지능 시간에 배웠던 스키마가 생각이 나서 x, y, z를 저장할 때 (x, y, z), (-1, y, z), (x, -1, z), (x, y, -1)로 저장했다.

-1은 무슨 값이 와도 된다는 뜻으로 넣었다.

 

이후에 차례대로 답을 카운트 할 때

현재 값이 x, y, z면 (-1, y, z)인 개수를 카운트에 더하고 현재 값과 같은 (x, y, z)의 개수를 빼준다(세 개 중 하나는 달라야 하기 때문)

나머지 (x ,-1, z)와 (x, y, -1)도 같은 방식으로 카운트하면 된다.

개수를 세고 나면 현재 x, y, z 값으로 저장했던 값들을 하나씩 빼준다.(중복)

 

시간제한이 4초길래 빡구현 문제인가 싶었는데 범위를 보니 커팅을 잘 해도 시간 초과가 날 것 같아서 다른 방법을 생각해 봤었다. tuple을 처음 사용해 봐서 구현하는 데 시간이 좀 걸렸다.

Div.3 C번 치고 어려운 편이었던 것 같다.

 

튜토리얼 코드도 나랑 비슷해서 뭔가 뿌듯한 느낌

이거 풀고 나니 민트 퍼포먼스가 떠있길래 잘하면 이번에 민트 퍼포를 띄울 수 있겠구나 생각이 들었다.

 

정답 코드 : https://codeforces.com/contest/1974/submission/261863665

 

D. https://codeforces.com/contest/1974/problem/D

Problem - D - Codeforces

rover와 helicopter가 있다.

NSEW, 네 방향을 가리키는 문자열이 주어졌을 때 최소한 한 번은 움직여서 rover와 helicopter가 같은 곳에 위치할 수 있는지 묻는 문제다.

 

R(rover)와 H(helicopter)가 같은 곳에 위치하려면 일단 N과 S가, E와 W가 홀수이면 안 된다.

또 SS 같은 경우는 각각 한 번씩 움직이면 되지만 NS와 같은 경우는 R이나 H 둘 중 하나만 움직여서 제자리에 도착할 수 있으므로 이런 경우를 예외 처리해 준다.

 

나머지는 R과 H의 북남동서 방향 카운트를 해서 NS는 R먼저 움직이고 R의 값이 더 크면 H를 움직이고 EW는 H 먼저 움직이고 H의 값이 더 크면 R을 움직이는 식으로 했다. NS와 EW별로 움직이는 주체를 바꾼 이유는 최소한 한 번씩은 움직여야 하기 때문이다.

 

예외 처리 후에 움직이는 코드를 짜는데 처음부터 저 방법을 생각하지 못했어서 2번 틀렸다. 

5분정도 남았을 때 저 방법이 생각나서 코드를 짜고 1분 남기고 제출했다.

1분 전에는 제출이 몰려들어서 맞았는지 확인을 못했지만 대회가 끝나고 맞았다고 떴다.

처음으로 버저비터를 성공해서 좋았다.

 

정답 코드 : https://codeforces.com/contest/1974/submission/261908133

Submission #261908133 - Codeforces

 

뒤에 E, F, G번은 시간이 없어서 살펴보지 못했는데 배낭 문제와 구현 문제들이 나왔다고 들었다.

일단 구현하는 데 시간이 너무 들어서 구현 실력을 키워야 점수가 더 오를 것 같다.

그리고 DP 문제들도 연습해야 될 것 같다.

 

 

기념샷과 함께 끝. (본계정보다 점수가 높아졌다)