[99클럽 코테 스터디] 37일차 TIL 완전 탐색

 

 

오늘의 문제는 백준

 

9094. 수학적 호기심

 

 

문제

 

 

 

문제 설명 

두 정수 n과 m이 주어졌을 때 0 < a < b < n 인 정수 쌍 (a, b) 중에서 (a^2 + b^2 + m) / (ab)가 정수인 쌍의 개수를 구하는 문제입니다. 

[입력]

첫 번째 줄 : 테스트 케이스의 개수 T가 주어집니다. 

다음 줄 : 각 테스트 케이스가 n과 m 한 줄로 주어집니다. 

[출력] 

각 테스트 케이스마다 문제의 조건을 만족하는 (a, b) 쌍의 개수를 출력합니다. 

 

[입력 예시]

3
10 1
20 3
30 4

[출력 예시]

2
4
5

 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 32분이 걸렸습니다.

 

 

 

문제 접근 방식

완전 탐색 방식으로 문제를 풀었습니다. countPairs 메서드를 통해 (a^2 + b^2 + m) / (ab)가 정수가 되는 쌍 (a, b)를 찾습니다. 중첩 반복문을 사용해 각 경우에 대한 분자와 분모를 계산하고 분자가 분모로 나누어 떨어질 때 cnt 값을 증가시켜 조건을 만족하는 쌍의 개수를 셉니다.

 

 

 

문제 풀이

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{

    static int T, n, m;

    public static int countPairs() {
        int cnt = 0; 

        for(int a = 1; a < n; a++) {
            for(int b = a + 1; b < n; b++) {
                
                int numerator = (int)Math.pow(a, 2) + (int)Math.pow(b, 2) + m;
                int denominator = a * b; 

                if(numerator % denominator == 0) {
                    cnt++; 
                }
                
            }
        }
        
        return cnt;
    }

    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            int answer = countPairs();
            System.out.println(answer);
        }



    }
}

 

 

Math.pow() 사용하기 

자바에서 거듭 제곱을 구하는 방법은 Math.pow()를 사용하는 것입니다. Math.pow(밑, 지수) 형식으로 사용할 수 있고 기본적으로 Double 타입으로 반환합니다. 때문에 문제에서 주어진 조건에 따라 int형으로 명시적 형변환을 하여 사용하였습니다. 아래는 Math.pow() 메서드를 활용한 코드입니다. 

int numerator = (int)Math.pow(a, 2) + (int)Math.pow(b, 2) + m;

 

 

 

 

 

 

 

 

 

이렇게 오늘 37일차 TIL을 작성해 보았습니다.