6064 카잉 달력

카잉 달력 (6064)

 

풀이코드 (틀림)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 6064 카잉달력
const int MAX = 40000;


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	int T;
	
	cin >> T;
	
	while(T-- > 0){
		int M, N, x, y;
		
		cin >> M >> N >> x >> y;
		
		int x1 = 1, y1 = 1;
		int count = 1;
		while(count <= MAX ){
			if(x1 == x && y1 == y){
				break;
			}
			if(x1 == M) {
				x1 = 1;
			}
			else{
				x1++;
			}
			if(y1 == N){
				y1 = 1;
			} 
			else{
				y1++;
			}
			count++;
		}
		count = count > MAX ? -1 : count;
		cout << count <<'\n';
	}
	
	
	
	
	
}

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 6064 카잉달력
const int MAX = 40000;


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	int T;
	
	cin >> T;
	
	while(T-- > 0){
		int M, N, x, y;
		
		cin >> M >> N >> x >> y;
		
		x -= 1;
		y -= 1;
		
		bool flag = false;
		// i 는 x 에 고정. x는 무조건 맞음
		for(int i = x; i < M * N; i += M){
			// i % N 이 y 와 같다. 정답이라면
			if(i % N == y){
				cout << i + 1 << '\n';
				flag = true;
				break;
			}
		}
		if(!flag)
			cout << -1 << '\n';
	}
	
	
	
	
	
}

해설

---

적용한 레시피 / 방법론 + 접근법

분명히 저번에 풀었던 달력 문제  와 일맥상통했다. 그래서, 보자마자 나머지를 이용한 풀이로 돌입하였는데, 1이 시작이라는 이유로 그냥 포기해버렸다.

 

그렇게 하지 않고, -1을 하여 나머지를 이용하는 방법으로 나아갔어야 했다.

풀이

위의 말처럼 모든 항에 -1을 하면, 0번째년 부터... M,N 번째 년까지 나올 것이다. 나머지를 이용한 것이기에 각 항은 x:y 가 아닌 i % M : i % N 으로 나타낼 수 있다.

일정한 규칙이 반복되므로, input 으로 들어오는 x 나 y 중 하나를 기준점으로 잡고 그 x 에 대한 y 의 변동만을 살펴봐서 답을 구해내는 것이 건너 뛰며 해보기 라고 할 수 있겠다.

 

왜 그냥 브루트 포스로 할 수 없는지가 선행되어야 하는 풀이인데, N 과 M 의 최대치가 40,000 이므로 NM 은 1,600,000,000 16억이 되어서 절대 시간내에 풀 수 없을 것이라는 점에서 착안해야한다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

- 풀어봤던 문제와 비슷하다고 같은 풀이법을 바로 적용한 점.

- 가능하지 않은 경우일 때의 케이스를 고려하지 않았던 점. 예외처리의 부족 

: bool 변수 flag 를 통해 해결

- 브루트 포스가 먹히지 않을 것이라는 점을 미리 파악하지 못하고, 단순한 브루트 포스로 접근한 점.

:

분명히 중요하고, 문제를 맞이했을 때 제일 먼저 해야하는 부분이다.