Prefix Sum - 2725

문제 설명

1. 입력으로 테스트 케이스 C가 주어진다.
2. C의 갯수만큼 자연수 N이 주어진다.
3. 각 테스트 케이스마다 0,0에서 보이는 점의 갯수를 출력한다.

문제 풀이

사용하는 알고리즘 설명

이 문제는 누적합(Prefix Sum)의 개념과 동적 프로그래밍(Dynamic Programming)의 개념이 같이 들어가있는 문제이다.

보통 누적합과 동적 프로그래밍은 같이 사용하는 경우가 많다고 한다.

 

이전 DP 문제들에서 i번째 값은 i-1번째 값과 i번째 값 중 최대값 이런식으로 작은 것부터 계산해서 올라온 것을 기억할 것이다.

이 방식이 누적합 방식이다.

 

예시

이 문제도 예를 들어 설명하겠다.

2,2를 구하려면

1,1의 점의 수는 3이다.

1,2의 점의 수는 4이다.

2,1의 점의 수는 4이다.

그렇다면 2,2의 점의 수는 1,2의 점의 수 + 2,1의 점의 수 - 1,1의 점의 수이다.

식으로 표현하면 아래와 같다.

 

vertex[2,2] = vertex[1,2] + vertex[2,1] - vertex[1,1]

다시 말하면 vertex[2,2] = vertex[1,1] + 2로도 표현할 수 있다.

 

x,y 좌표가 둘의 최대 공약수를 구해서 서로소인 경우(최대 공약수가 1인 경우) 0,0에서 보이는 새로운 점이다.

ex) 4,2의 경우 최대 공약수가 2로 나누면 2,1의 점이 가리고 있기 때문에 0,0에서 보이지 않는다.

 

그리고 0,0에서 보이기 때문에 대칭인 점은 반드시 보인다는 것을 이용하면 다음과 같이 표현할 수 있다.

if(x와 y의 최대 공약수 == 1) 점 갯수 +2

이걸 반복문으로 표현해서 1000개의 점을 먼저 계산할 것이다.

코드 풀이

using System;
using System.Collections.Generic;
using System.Linq;

namespace StudyCS
{
    class Program
    {
        public static void Main(string[] args)
        {
            // N=1000까지의 모든 정답을 미리 계산
            long[] dp = new long[1001];
            dp[1] = 3;

            for (int i = 2; i <= 1000; i++)
            {
                int newPoints = 0;
                for (int k = 1; k < i; k++)
                {
                    if (Gcd(i, k) == 1)
                    {
                        newPoints += 2; // (i, k)와 (k, i) 두 점이 추가됨
                    }
                }
                dp[i] = dp[i - 1] + newPoints;
            }

            // 테스트 케이스 처리
            int C = int.Parse(Console.ReadLine());
            long[] result = new long[C];
            for (int i = 0; i < C; i++)
            {
                int N = int.Parse(Console.ReadLine());
                result[i] = dp[N];
            }
            for (int i = 0; i < C; i++)
            {
                Console.WriteLine(result[i]);
            }
        }
        public static int Gcd(int a, int b)
        {
            //유클리드 호제법
            while(b != 0)
            {
                int temp = b;
                b = a % b;
                a = temp;
            }
            return a;
        }
    }
}

여기서 특이한 점은 Gcd 함수(최대 공약수를 구하는 함수)가 유클리드 호제법으로 작성된 것이다.

유클리드 호제법이란?

"호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다."고 위키피디아에 적혀있다.

유클리드 호제법 - 위키피디아

 

좀 쉽게 설명하자면 두 수 A, B가 주어질 때 이 둘을 나눈 나머지와 b의 최대 공약수와 같다.

예시) 10, 4가 주어진다면 나눈 나머지 2가 나온다. 그렇다면 4와 2의 최대 공약수와 같다.

4와 2의 나눈 나머지가 0이기 때문에 최대 공약수는 나누는 값인 2이다. 따라서 10과 4의 최대 공약수도 2이다.