[백준 / BOJ] C++ 27965 N결수

27965번: N결수

 

문제

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

27965번: N결수

 

 

풀이

N결수를 만들고 K로 나누기엔 N결수가 너무 큰 수가 되기 때문에 long long의 범위를 벗어나게 된다. 따라서 과정을 쪼개 중간중간에 나머지 연산을 해야한다.

 

N = 5, K = 7인 경우를 예로 들면, 1~5를 차례대로 나열해야한다.

이때 1을 K로 나눈 나머지 1을 저장한다.

저장해둔 1을 다시 가져와 2를 이어붙여 12가 되고 이를 다시 K로 나눈 나머지 5를 저장한다.

다시 53을 K로 나눈 나머지는 4가 되고, 44를 K로 나눈 나머지는 2, 25를 K로 나눈 나머지는 4가 된다.

따라서 정답은 4.

 

위와 같은 방식으로 처리하게 되면 long long의 범위를 벗어나지 않고 해결할 수 있다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, k;
  cin >> n >> k;
  string s = "0";
  for (int i = 1; i <= n; i++) {
    s += to_string(i);
    long long num = stoll(s);
    num %= k;
    s = to_string(num);
  }
  cout << s;
  return 0;
}