#1 문제
1-1. 분류
- 플랫폼: 백준 BOJ
- 문제 번호: 31629
- 대회명: 2024 가지컵
- 난이도: 다이아몬드 5
- 알고리즘: 수학, 애드 혹, 정수록, 확장 유클리드 호제법
1-2. 전문
1-3. 입력 및 출력
#2 문제 풀이
문제의 시간 제한과 테스트 케이스, n의 범위를 고려하였을 때 시간 복잡도 O(n) 알고리즘 조차도 시간 초과가 발생하는 어려운 문제이다. 이런 경우에 시간 제한을 충족하기 위해 수식을 활용하여 문제를 간단히 풀 수 있어야 한다.
2-1. 가지 밭의 수식
이 문제에서는 가지 밭을 수식으로 나타내는 형식으로 문제를 간단히 풀이할 수 있다. 두 종류의 가지 밭을 수식으로 나타내고, 두 수식이 일치하는 근을 찾았을 때 이 값들이 가지 밭의 길이가 될 수 있다. 먼저 첫 번째 가지밭의 경우 n * 행의 수 + 열의 수를 통해 쉽게 수식으로 나타낼 수 있다.
두 번째 가지밭의 수식은 행과 열까지의 칸을 개수를 세는 방식으로, 현재 행과 열까지를 도형으로 세 등분 하여 나타낼 수 있다.아래 그림에서 r,c의 값을 알고 싶다면 파란색 사각형의 (r-1)*(r*c), 빨간색 삼각형의 1 + 2 + ... + c, 초록색 삼각형의 1 + 2 + ... + r을 다 더하여 구할 수 있다. 수식을 간단히 정리하면 아래와 같다.
2-2. 근 찾기
하지만 수식으로 나타낸 가지 밭을 n까지의 루프를 통해 근을 찾는 방법은 시간 복잡도 O(n)으로, n의 범위가 10억이 넘는 문제의 상황에서는 시간 초과가 발생한다. 더욱 낮은 시간 복잡도에서 근을 찾을 수 있는 방법을 찾아야 한다.
풀이 중
참고 자료