[백준] 2725번. 보이는 점의 개수(JAVA)

문제

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

---

풀이(12분)

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] count = new int[1001]; // 보이는 점 개수 저장 배열
        count[1] = 3; // 초기값 설정

        for (int i = 2; i <= 1000; i++) {
            int visiblePoints = 0;
            for (int j = 1; j < i; j++) {
                if (gcd(i, j) == 1) visiblePoints++;
            }
            count[i] = count[i - 1] + visiblePoints * 2;
        }

        int C = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while (C-- > 0) {
            int n = Integer.parseInt(br.readLine());
            sb.append(count[n]).append("\n");
        }

        System.out.print(sb);
    }

    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

---

문제 풀이 전략

문제를 보았을 때 탄젠트를 먼저 떠올렸다. 하지만 라이브러리를 사용하여 탄젠트를 구현할 수가 없기 때문에 기약분수로 만들었을 때 다르다는 것을 생각했다.

 

따라서 집합에 추가하는 방식으로 구현해보려고 하였으나 메모리 초과가 발생하는 문제가 있었다.

지나치게 많은 연산을 수행하고, 이것을 저장하고 있었기에 발생한 문제였다.

 

최종적으로 1차원 배열에 이를 저장함으로써 dp적인 문제로 해결할 수 있었다.