Codeforces Round #789 (Div. 2) D. Tokitsukaze and Meeting

Problem - D - Codeforces

그냥 구현 문젠데 어려워서 정리

잘 관찰만 하면 되는데 그게 어려운 문제

행과 열을 각 각 따로 계산해서 더해줘야 한다.

 

행에서는 m개의 요소가 계속 돌면서 채워주기 때문에

행 카운트는 항상 단조 증가한다.

m개의 요소가 계속 돌기 때문에 만약 안 채워져 있으면 카운트를 1 증가시켜주고 채워주면 된다.

 

열에서의 관찰이 조금 어려웠는데

일일이 1이 들어오는 경우의 수를 따지다 보니까 굉장히 문제가 어려워졌다.

사실 열에서도 m개의 요소가 사이클을 도는 건 맞지만 한 번 돌 때마다 새로운 m개의 요소가 앞에 추가가 된다.

m개의 요소가 사이클을 도니까 m번마다 열 카운트가 반복될 것이다.

반복될 때마다 새로운 요소 한 줄이 맨 앞에 붙으니까 맨 앞줄에 1이 있다면 1을 증가시켜주면 된다.

다시 말해서 m번마다 열 카운트가 반복되니까 배열 int arr[m] 이 필요할 것이다.

i%m 마다 맨 앞줄에 1 이 있는지 확인하고 있으면 arr[i%m]을 1 증가시켜 주면 된다.

맨 앞줄에 1이 있는지 확인하는 방법은 마지막 1이 들어왔을 때의 인덱스를 last로 저장해준다.

만약 현재 확인하려는 i번째 인덱스가 last와의 차이가 m보다 작다면 맨 앞줄에 1이 존재하는 것이다.

 

일일이 경우의 수를 따져보는 것도 좋지만 먼저 m개마다 반복된다는 그 사실에 집중하고 반복이 되니까 따로따로 저장을 해야 한다는 것까지가 핵심 생각인 것 같다.