백준 1422 숫자의 신

작성일 | In |

Problem : 숫자의 신

유형 : 그리디

문제 해석

  • 입력으로 들어오는 K개의 수를, 각자 최소 한번씩 이용하여 총 N번을 사용하라.
  • 이때 K <= N <= 1000 이다.
  • {2,3,7} (K = 3), 일때 N이 4인경우 전부 한번씩 사용하고(3) 732 + 7은 한번더 사용하여(1) 답은 7732가 된다.
  • 숫자는 자연수만 들어오고 10억 이하이다.

해결전략

  • 바로 이전 풀었던 16496 큰수만들기와 굉장히 유사한 문제이다.
  • 정렬을 시키는데 정렬기준을 두개의 수를 연결했을때, 가장 큰수가 되는 방법으로 정렬한다.
  • N이 K보다 큰경우, 값으로 가장 큰 숫자가 해당 숫자가 나오는 위치에서 반복되어야 한다.
    • {7, 88 9} 이 있고 4번사용되어야 한다면 88이 제일크므로
    • 결과는 9/88/88/7 이 되어야한다.

구현

  • 정렬기준을 문자열 기준 num1 + num2 > num2 + num1 으로 잡는다.
  • N이 K보다 큰 경우, 가장 큰숫자를 찾고 N-K횟수만큼 반복해 출력한다.
  • 가장 큰숫자를 찾는 과정은 어차피 N이 1000이하이므로 O(N)으로 그냥 한번 돌며 찾으면된다.

주의할점

  • 이 문제에서는 0을 자연수로 삼지 않는다.
  • 0을 자연수로 생각하느냐는 그떄 그떄 다르다…
  • 정규 교과 과목에서는 자연수로 삼지않고, 이산수학과 같은 고등 과정에서는 자연수로 삼는다.
    • https://www.acmicpc.net/board/view/52247
    • 개인적으로 양의 정수, 혹은 0을 포함한 양의 정수로 표현해주었으면 좋겠다..

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

using namespace std;

void solve();

bool cmp(const string &num1, const string &num2);

string getMaxNum(const vector<string> &numbers);

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  freopen("input.txt", "r", stdin);

  solve();

  return 0;
}

void solve() {
  int k, n;
  int diff;
  vector<string> numbers;

  cin >> k >> n;
  diff = n - k;
  for (int i = 0; i < k; ++i) {
    string number;
    cin >> number;
    numbers.push_back(number);
  }

  sort(numbers.begin(), numbers.end(), cmp);

  string maxNum = getMaxNum(numbers);

  for (const string &number : numbers) {
    while (diff > 0 && number == maxNum) {
      cout << number;
      diff--;
    }
    cout << number;
  }
}

string getMaxNum(const vector<string> &numbers) {
  int maxNum = 0;
  for (const string &number : numbers) {
    maxNum = max(maxNum, stoi(number));
  }
  return to_string(maxNum);
}

bool cmp(const string &num1, const string &num2) {
  if (num1 == num2) return true;
  return num1 + num2 > num2 + num1;
}

참고, 피드백

인풋

1
2
3
4
5
6
7
8
7 8
92
91
9
78
7
888
76

Mac

1
2
3
4
5
Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/4.2.1
Apple clang version 12.0.5 (clang-1205.0.22.9)
Target: x86_64-apple-darwin20.4.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

image

  • Mac 컴파일 정렬 결과

ideone c++14, mingw

https://ideone.com/xmtavm

image

  • 온라인 IDE ideone 정렬 결과

  • 아직도 이해할 수 없지만 MAC의 g++ 에서 정렬이 자꾸 이상하게 수행 되었다.
  • 처음에는 clion 문제인가 싶어서, 콘솔에서도 직접 g++ 명령을 통해 컴파일을 시도해보았지만 여전히 결과가 이상하게 나왔다..
  • 사진은 없지만 데스크탑의 mingw로도 ideone 와 같은 결과를 내놓았따.
  • 계속 내 로직상의 문제인가 싶어서 삽질했는데…. 원인은 아직 찾지 못했고, 앞으로도 비슷한 일이 생기면 온라인 IDE로 한번 컴파일을 해보아야곘다.
    • 어차피 cpp는 ps 용으로만 사용할꺼기 떄문에, 개발에는 영향없으니!

왜 이런 문제가 발생하는지 아시는분은 댓글 꼭 달아주세요!!