글 읽기 - 어떤 테스트케이스들이 더 필요할까요?

redsiwon 4년 전 5

아래는 제가 직접 테스트해본 결과들입니다.

밑에 놈들은 잘 되는데 3%에서 틀렸습니다 뜨네요.

혹시 제 테스트 케이스나 코드에서 잘못된 부분을 보고 알려주시면 참 감사드리겠습니다.

input:
2
1 50
50
output:
1

input:
2
2 1
10
output:
1111111111

input:
10
1 1 1 1 1 1 1 1 1 1
50
output:
99999999999999999999999999999999999999999999999999

input:
3
6 7 8
21
output:
210

input:
3
6 7 8
22
output:
211

input: ****#### 중요
3
5 7 8
21
output:
220

input:
3
6 7 8
7
output:
1

input:
3
6 7 8
6
output:
0

input:
1
10
20
output:
0

input:
5
1 2 2 3 3
20
output:
2000000000000000000

input:
3
10 30 50
20
output:
0

input:
10
6 32 38 18 12 6 7 8 6 7
50
output:
99888888

#include <iostream>
#include <string>

const int THRESHOLD = 9E7;
int a_cost[10], a_count[10];
int n, money;

int main()
{
    std::cin >> n >> a_cost[0];
    int min_cost = 51, min_pos = 0;
    for (int i = 1; i < n; ++i) {
        std::cin >> a_cost[i];
        if (min_cost >= a_cost[i]) { // cost 같을 때 큰 수 선호 => 등호 붙임
            min_cost = a_cost[i];
            min_pos = i;
        }
    }
    std::cin >> money;
    if (n == 1 || money < min_cost) {
        std::cout << "0" << std::endl;
        return 0;
    }

    // 1~9 제일 싼 거 1개
    int temp_money = money;
    ++a_count[min_pos];
    temp_money -= min_cost;

    // 0~9 제일 싼 거 최대로
    if (min_cost > a_cost[0]) {
        min_cost = a_cost[0];
        min_pos = 0;
    }
    int quot = temp_money / min_cost;
    a_count[min_pos] += quot;
    temp_money -= quot * min_cost;

    // 더 큰 수로 1개씩 바꿔치기
    for (int i = 0; i < n - 1; ++i) {
        int j = n - 1;
        while (a_count[i] > 0 && j > i)
            if (temp_money + a_cost[i] - a_cost[j] < 0)
                --j;
            else {
                temp_money += a_cost[i];
                temp_money -= a_cost[j];
                --a_count[i];
                ++a_count[j];
            }
    }

    std::string result = "";
    int temp_result = 0;
    for (int i = 9; i > 0; --i)
        while (a_count[i]-- > 0) {
            temp_result *= 10;
            temp_result += i;
            if (temp_result > THRESHOLD) { // 임계값 넘으면 문자열에 붙이기
                result += std::to_string(temp_result);
                temp_result = 0;
            }
        }
    if (temp_result > 0)
        result += std::to_string(temp_result);
    result += std::string(a_count[0], '0'); // 0 갯수만큼 복사해서 붙이기
    std::cout << result << std::endl;
    return 0;
}

gumdung 4년 전 2

input:
3
6 7 8
22
output:
211

이 케이스는

220(8+8+6) 이어야지 않을까요??

별개로 저도 해매고 있네요 ㅠ

redsiwon 4년 전 1

gumdung님 감사합니다.

아예 예상답을 잘못생각했었네요 ㅋㅋ;

redsiwon 4년 전 1

다른 테케 여전히 잘 되고, 지적해주신 부분에 대해서도 고쳤는데

바로 틀렸습니다 나오네요 ㅋㅋ

redsiwon 4년 전 1

// 더 큰 수로 1개씩 바꿔치기

이 부분 로직 수정하니까 맞았네요.

감사합니다 ㅋㅋ

powwow101 1년 전 0

input:
1
10
20
output:
0

와 이거에서 살아갑니다 감사합니다 ㅠㅠ...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 테스트케이스들이 더 필요할까요?

redsiwon 4년 전 5

gumdung 4년 전 2

redsiwon 4년 전 1

redsiwon 4년 전 1

redsiwon 4년 전 1

powwow101 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말