하나의 정수 num이 입력으로 주어졌을 때, 1부터 num 사이 범위에 있는 i와 j에 대해 ((num % i) % j) % num의 값이 최대가 되도록 만드는 (i, j) 쌍의 개수를 구하는 것이 목표입니다.
문제 예시로 이해하기
- 입력 − num = 4
- 출력 − ((n % i) % j) % n이 최대가 되는 (i, j) 쌍의 개수: 3
- 설명 − 해당하는 쌍은 (3,2), (3,3), (3,4)입니다.
- 입력 − num = 6
- 출력 − ((n % i) % j) % n이 최대가 되는 (i, j) 쌍의 개수: 4
- 설명 − 해당하는 쌍은 (4,3), (4,4), (4,5), (4,6)입니다.
방법 1: 완전 탐색(Brute Force)
어떤 수를 절반에 가까운 값으로 나눌 때 나머지가 가장 커진다는 성질을 활용합니다. 즉, temp = num/2 + 1로 설정하면 최대 나머지는 total = num % temp가 됩니다. 이후 i와 j를 1부터 num까지 모두 탐색하면서 ((num % i) % j) % num의 값이 total과 일치하는 경우를 모두 세면 됩니다.
알고리즘 단계
- 정수 num을 입력받습니다.
- 함수 maximized_pair(int num)은 num을 받아 조건을 만족하는 (i, j) 쌍의 개수를 반환합니다.
- count를 0으로 초기화합니다.
- 나머지가 최대가 되도록 num을 절반으로 나누는 값을 설정합니다. temp = (num / 2) + 1
- 최대 나머지를 계산합니다. total = num % temp
- 두 개의 for 반복문을 사용해 i와 j를 [1, num] 범위에서 탐색합니다.
- ((num % i) % j) % num의 값이 total과 같으면 count를 1 증가시킵니다.
- 모든 반복이 끝나면 count를 결과로 반환합니다.
방법 2: 효율적인 접근(O(1))
마찬가지로 최대 나머지를 total = num % temp(temp = num/2 + 1)로 구합니다. 최대 나머지를 만들어 내는 i는 사실상 고정되어 있으므로, j만 total보다 큰 값부터 num까지 자유롭게 선택하면 ((num % i) % j) % num의 값이 계속 total로 유지됩니다. 따라서 가능한 쌍의 개수는 num − total이 됩니다.
단, num = 2인 경우에는 (1,1), (1,2), (2,1), (2,2) 네 가지 쌍이 모두 가능하므로 4를 바로 반환해야 하며, num − total 공식으로는 계산할 수 없습니다.
알고리즘 단계
- 정수 num을 입력받습니다.
- 함수 maximized_pair(int num)은 num을 받아 조건을 만족하는 (i, j) 쌍의 개수를 반환합니다.
- count를 0으로 초기화합니다.
- num이 2이면 4를 반환합니다.
- 그렇지 않으면 temp = (num / 2) + 1로 설정합니다.
- 최대 나머지를 계산합니다. total = num % temp
- count = num − total로 설정합니다.
- count를 결과로 반환합니다.
예제 코드 (완전 탐색)
#include<bits/stdc++.h>
using namespace std;
int maximized_pair(int num){
int count = 0;
int temp = ((num / 2) + 1);
int total = num % temp;
for (int i = 1; i <= num; i++){
for (int j = 1; j <= num; j++){
int check = ((num % i) % j) % num;
if (check == total){
count++;
}
}
}
return count;
}
int main(){
int num = 10;
cout<<"Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: "<<maximized_pair(num);
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6
예제 코드 (효율적인 접근)
#include<bits/stdc++.h>
using namespace std;
int maximized_pair(int num){
int count = 0;
if (num == 2){
return 4;
}
else{
int temp = ((num / 2) + 1);
int total = num % temp;
count = num - total;
}
return count;
}
int main(){
int num = 10;
cout<<"Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: "<<maximized_pair(num);
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6