[BOJ] 1437번 수 분해

복기

처음엔 메모이제이션을 생각했는데, 수학 문제는 해당 수의 규칙성을 잘 발견해야겠다.

코드

• C++ 17

#include <stdio.h>   #define M 10007   using uint = unsigned;   int main() {     uint n = 0;     scanf("%u", &n);       // N이 5 미만이라면 분해를 하지 않고 그대로 곱하는 것이 이득이고     // N이 5 이상이라면 3을 가능한 많이 곱하는 것이 이득이다.     uint k = 1;     while (n >= 5)     {         k *= 3;         k %= M;         n -= 3;     }     printf("%u", (n * k) % M); }

• C# 6.0

using System; using System.Diagnostics.CodeAnalysis;   namespace Csharp {     class Program     {         static int N;                  static void Main(string[] args)         {             N = Convert.ToInt32(Console.ReadLine());                          int K = 1;             while (N >= 5)             {                 K *= 3;                 K %= 10007;                 N -= 3;             }               Console.Write(N * K % 10007);         }     } }

• Python 3

from sys import stdin, setrecursionlimit input = stdin.readline   N = int(input())   K = 1 while N >= 5:     K *= 3     K %= 10007     N -= 3   print(N * K % 10007)