[백준/C++] 1422번: 숫자의 신

2025. 5. 22. 16:25· Koala - 18기/코딩테스트 심화 스터디
목차
  1. 문제 & 링크
  2.  
  3. 풀이
  4. 코드

문제 & 링크

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

 

풀이

1. K개의 수를 적어도 한 번씩 사용해야 하기에, 모든 수를 이어 붙여서 가장 큰 수를 구하는 문제와 유사하다.

2. N > K일 경우 숫자를 중복으로 사용하여 추가할 수 있는데, 자릿수와 값을 생각하면 무조건 K개의 수 중 큰 수를 N - K 만큼 붙여야 한다.

3. 숫자를 string으로 바꾸어 사전 순으로 가장 앞서는 수를 구한다. 숫자를 그냥 넣게 될 경우, 아래와 같은 예시가 존재할 수 있다.

  ex) K = { 31, 34 } -> 사전 순으로 정렬: 34, 31 -> 결과: 3431 (기댓값: 3431)

  ex) K = { 3, 34 } -> 사전 순으로 정렬: 34, 3 -> 결과: 343 (기댓값: 343)

  ex) K = { 3, 31 } -> 사전 순으로 정렬: 31, 3 -> 결과: 313 (기댓값: 331)

4.  맨 앞부터 시작하여 대소 관계를 비교(우선순위큐가 자동으로 실행)하고, 만약 비교할 숫자가 없을 경우, 제일 앞 숫자와 비교한다.

  ex) K = {3, 34}

3과 34에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 X & 4 (X: 제일 앞 숫자인 3으로 생각) -> 결과: 343

  ex) K = {3, 31}

3과 31에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 X & 1 (X: 제일 앞 숫자인 3으로 생각) -> 결과: 331

5. 비교할 숫자가 없어서 제일 앞 숫자와 비교했는데, 같은 값일 경우 그 다음 숫자를 비교한다.

  ex) K = {34, 343}

34와 343에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 4 & 4, 다음 자리 비교 X & 3 (X: 제일 앞 숫자인 3으로 생각), 다음 자리 비교 X2 & Y (X2: 제일 앞에서 두 번째 숫자인 4로 생각, Y: 제일 앞 숫자인 3으로 생각) -> 결과: 34343

  ex) K = {31, 313}

31과 313에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 1 & 1, 다음 자리 비교 X & 3 (X: 제일 앞 숫자인 3으로 생각), 다음 자리 비교 X2 & Y (X2: 제일 앞에서 두 번째 숫자인 1로 생각, Y: 제일 앞 숫자인 3으로 생각) -> 결과: 31331

6. 3 - 5번의 내용을 구현하기 위해 입력 받은 값을 10번 반복하여 붙이고, 우선순위큐에 저장한다. 10번 반복하는 이유는 가장 큰 입력값인 1,000,000,000을 무조건 넘게 하기 위함이다.

7. 2번의 case일 경우를 위해 미리 가장 큰 수를 저장해놓고, 우선순위큐에서 pop되는 시점에 N - K만큼 붙인다.

  ex) K = 2 ({3, 34}), N = 3, 가장 큰 수: 34

3과 34에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 X & 4 (X: 제일 앞 숫자인 3으로 생각) -> 결과: 34343

  ex) K = 2 ({3, 31}) , N = 4, 가장 큰 수: 31

3과 31에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 X & 1 (X: 제일 앞 숫자인 3으로 생각) -> 결과: 3313131

 

코드

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main() {
    priority_queue<string> pq;
    int K, N;
    string ans = "";

    cin >> K >> N;

    string S;
    int max_value = 0;
    for (int i = 0; i < K; i++) {
        cin >> S;
        string tmp = S;
        max_value = max(max_value, stoi(S));

        for (int j = 0; j < 9; j++) tmp += S;

        pq.push(tmp);
    }

    bool empty = true;
    while (!pq.empty()) {
        string str = pq.top();
        pq.pop();

        str = str.substr(0, str.length() / 10);

        if (empty && stoi(str) == max_value) {
            for (int i = 0; i < N - K; i++) {
                ans += str;
            }
            empty = false;
        }

        ans += str;
    }

    cout << ans;
}
저작자표시 (새창열림)

'Koala - 18기 > 코딩테스트 심화 스터디' 카테고리의 다른 글

[백준/C++] 1294번: 문자열 장식  (0) 2025.05.22
[백준/C++] 13911번: 집 구하기  (0) 2025.05.22
[백준/C++] 5972번:택배 배송  (0) 2025.05.18
[백준/python] 6186 Best Grass  (0) 2025.05.10
[백준/python] 2164: 카드2  (0) 2025.05.04
  1. 문제 & 링크
  2.  
  3. 풀이
  4. 코드
'Koala - 18기/코딩테스트 심화 스터디' 카테고리의 다른 글
  • [백준/C++] 1294번: 문자열 장식
  • [백준/C++] 13911번: 집 구하기
  • [백준/C++] 5972번:택배 배송
  • [백준/python] 6186 Best Grass
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
Koala항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1884)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • C++
  • 백준
  • BOJ
  • BFS
  • dp
  • 백트래킹
  • dfs
  • 파이썬

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[백준/C++] 1422번: 숫자의 신
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.