[C#] 백준 1964번 오각형, 오각형, 오각형…

[ 문제 ]

오각형의 각 변에 아래 그림과 같이 점을 찍어 나간다. N단계에서 점의 개수는 모두 몇 개일까?

 

[ 코드 ]

1. 내 코드 

using System.Numerics;

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

int n = int.Parse(sr.ReadLine());

BigInteger result = 5;
BigInteger num = 7;

for (int i = 2; i <= n; i++)
{
    result += num;
    num += 3;
    result %= 45678;
}

sw.Write(result);

sw.Flush();
sr.Close();
sw.Close();

 

2. 다른 사람 코드 참고

using System.Numerics;

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

long n = int.Parse(sr.ReadLine());

BigInteger result = (((3 * n * n) + 5 * n) / 2 + 1) % 45678;

sw.Write(result);

sw.Flush();
sr.Close();
sw.Close();

 

[ 풀이 ]

등차수열의 합 공식. 점은 2번 부터 2번 새로 추가된 점 (7개) + 3번 새로 추가된 점(10개) ... 3씩 증가함.

 

1. ((n * n) + n) / 2에서 3씩 증가하기 때문에 3n * n 이 된다. 

2. ((3 * n * n) + n) / 2 에서 5각형의 점의 개수를 세야하기 때문에  5 * n

3. ((3 * n * n) + (5 * n)) / 2 에서 / 2는 불필요한 중복 값 제거

4. ((3 * n * n) + (5 * n)) / 2 + 1 해주는 이유는 층마다 한 변에 점이 1씩 증가하기 때문

5. %45678은 값이 너무 커지는 것을 방지하여 나누어주는 것

long a = ((1 + n) * n) / 2; // 등차수열 공식
BigInteger result = (a * 3 + n + 1) % 45678;

 이렇게 하는게 더 편할 것 같다. 

 

[ 실행화면 ]

case: 1

---

문제링크: https://www.acmicpc.net/problem/1964

1964번: 오각형, 오각형, 오각형…