반응형
문제설명
https://www.acmicpc.net/problem/6064
사고과정
- 처음에 while문으로 하려했으나 시간초과가 발생할 뿐만 아니라 유효하지 않은 경우의 수를 필터링하지 못했다. 그래서 힌트를 보고 DP를 활용해 구현하려 했지만 이것도 모든 테스트를 통과하지 못했다..
- 그래서 풀이를 보았는데, 특정 규칙을 찾는 것이 관건이었다. 이 규칙을 찾기 위해서는 "하나만 생각" 하고 "원형 리스트"를 생각하면 될 것 같았다. 여기서 원형 리스트란 무엇이냐? 바로 %(나머지 연산)을 사용해서 다시 리스트 인덱스 앞으로 이동하는 것을 말한다. 예를 들어, [1,2,3,4] 가 있을 때, 인덱스가 5번이라고 한다면 값을 넘어가기 때문에 다시 초기화해서 돌아가야 한다. 이 때 5 % 4(리스트 길이)를 하게 되면 1이 되는데 이는 곧 1번 인덱스를 의미한다. 이와 비슷하게 이 문제에도 적용할 수 있는 듯 했다.
- 우선 x, y가 다시 1로 돌아가는 조건인 M, N이 주어졌다. 따라서 x, y가 M, N보다 커질 때 1로 회귀하는데, 이 때 %연산자를 활용한다.
- 그리고 x는 어차피 M을 계속 더해도 M보다 커지면 다시 1로 회귀하게 된다. 따라서 x를 고정시키고 y와 y의 범위인 N을 활용할 수 있다.
- 예를 들어, M = 10, N = 12, x = 3, y = 9 라고 할 때, x인 3을 N인 12로 나머지 연산을 한 값과 y인 9와 N인 12를 나머지한 연산 결과값이 같다면 그 때의 x 값이 바로 정답을 의미한다. 이 때, 나머지 한 연산 결과값이 서로 다를 때마다 x에다가 x의 범위인 M을 더해준다. 그래야 x가 1로 회귀하는 동안 증가한 해(year)를 셀 수 있기 때문이다.
- 뭔가 수학문제를 푸는 것 같았다. 상당히 어렵다..
풀이(스스로 못 푼 풀이)
import sys
input = sys.stdin.readline
for tc in range(int(input())):
m, n, x, y = map(int, input().split())
flag = True
while x <= n*m:
if x % n == y % n:
print(x)
flag = False
break
x += m
if flag:
print(-1)
반응형
'알고리즘 삽질장' 카테고리의 다른 글
[인프런] 사과나무(다이아몬드) (0) | 2021.11.12 |
---|---|
[BOJ] 1748번 - 수 이어 쓰기 1 (0) | 2021.11.05 |
[BOJ] 14500번 - 테트로미노 (0) | 2021.11.05 |
[BOJ] 1107번 - 리모컨 (0) | 2021.11.04 |
[BOJ] 1476번 - 날짜 계산 (0) | 2021.11.03 |