Algorithm/문제풀이

[BOJ] 백준 9094 - 수학적 호기심 - Java

Razelo 2021. 7. 18. 17:35

 

오랜만에 시간이 남아서 백준 9094문제를 풀어보았다. 

티어도 브론즈로 낮아서 쉽게 풀 수 있었는데, 왜인지 속도가 너무 느렸다. 

그래서 계속해서 코드를 바꿔보면서 시도했는데도 코드가 너무 느려서 처음에는 반목문안에 있는 sysout 출력문이 문제라고 생각해서 

StringBuilder에 결과를 모두 append 해준 다음에 반복문 밖에서 출력해주는 걸로도 바꾸었는데 소용이 없었다. 

 

그러다가 if문 안에 있는 Math.pow(j, 2) 를 j * j 로 바꾸었더니... 결과는 위에 표를 보면 알겠지만., 

1556에서 372까지 속도가 줄어들었다.

 

이제부터는 Math.pow 를 통해 제곱하지 말고 j*j를 통해 그냥 제곱해주자.

 

Math.pow는 반복문안에서 함수를  계속 호출하는 셈이었으니  속도가 느릴 수 밖에 없었다. 

 

필연적으로 함수호출은 스택에 계속 쌓임으로써 속도가 느릴 수 밖에 없다. 

다음부터는 이런 것들도 주의하면서 코드를 짜야겠다. 사소한 코드이더라도 주의를 기울이지 않으면 효율성에 영향을 미친다. 

 

https://www.acmicpc.net/problem/9094

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	public static boolean[][] arr; 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(st.nextToken());
		int count = 0;
		int n = 0;
		int m = 0; 
		
		for(int i = 0; i< T; i++) {
			st = new StringTokenizer(br.readLine()," ");
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			for(int j = 1; j<n; j++) {     //a
				for(int k = j+1; k<n; k++) { // b 
					if((j*j + k*k + m)%(j*k) == 0) { //나머지가 없다면 나누어떨어진다는 뜻!! 
						count++;
					}
				}
			}
			sb.append(count+"\n");
		    count = 0;
		}
		System.out.println(sb);
	}
}

 

반응형