[SWEA/C++] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금(D3)

풀이 시간: 1h06m20s

시간 복잡도: O(nC2^M) -> n: 문자열 길이, M: 교환 횟수

공간 복잡도: O(1) -> 상수 값에 의존

참고 자료: https://eunchanee.tistory.com/149

문제

퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다.

우승자는 주어진 숫자판들 중에 두 개를 선택에서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다.

예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 2회라고 하자.

교환전>

처음에는 첫번째 숫자판의 3과 네 번째 숫자판의 8을 교환해서 8, 2, 8, 3, 8이 되었다.

다음으로, 두 번째 숫자판 2와 마지막에 있는 8을 교환해서 8, 8, 8, 3, 2이 되었다.

정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금이 계산된다.

숫자판의 오른쪽 끝에서부터 1원이고 왼쪽으로 한자리씩 갈수록 10의 배수만큼 커진다.

위의 예에서와 같이 최종적으로 숫자판들이 8,8,8,3,2의 순서가 되면 88832원의 보너스 상금을 획득한다.

여기서 주의할 것은 반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다.

다음과 같은 경우 1회의 교환 횟수가 주어졌을 때 반드시 1회 교환을 수행하므로 결과값은 49가 된다.

94의 경우 2회 교환하게 되면 원래의 94가 된다.

정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산해보자.

입력

가장 첫 줄은 전체 테스트 케이스의 수이다.

최대 10개의 테스트 케이스가 표준 입력을 통하여 주어진다.

각 테스트 케이스에는 숫자판의 정보와 교환 횟수가 주어진다.

숫자판의 정보는 정수형 숫자로 주어지고 최대 자릿수는 6자리이며, 최대 교환 횟수는 10번이다.

출력

각 테스트 케이스마다, 첫 줄에는 “#C”를 출력해야 하는데 C는 케이스 번호이다.

같은 줄에 빈 칸을 하나 사이에 두고 교환 후 받을 수 있는 가장 큰 금액을 출력한다.

문제 풀이

교환 횟수 num의 경우에는 만약 교환 횟수가 문자열 크기보다 크다면 문자열 길이를 넘어가는 교환은 기존 숫자와 동일한 숫자를 얻을 뿐이고 시간 초과가 날 가능성이 높다.

if (num > str.size()) num = str.size();

위 코드는 교환 횟수를 문자열 크기 값으로 설정하는 코드인데, 이 부분을 추가했더니 시간초과가 나지 않았다.

 

그리고 교환 과정 같은 경우에는 dfs 알고리즘을 사용하여 재귀 방식으로 계산해주었다.교환 횟수가 모두 끝났을 경우 계산된 값들 중 가장 큰 결괏값을 도출하도록 하였다.

 

swap 함수를 두 번 실행해준 이유는 다음 시작점 i를 위해 문자열을 다시 원래대로 돌려놓기 위함이다.

 

오류 원인

result 값을 따로 출력하지 않고 그냥 max(result, stoi(str)) 부분을 그대로 리턴해 출력하려고 했다가 수정했다.

전체 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string str; // 입력된 숫자를 string으로 저장
int result, num; // 결괏값, 교환 횟수
 
void dfs(int n, int curNum) {
    // 교환 횟수가 모두 다 끝났을 경우, 가장 큰 값 저장. stoi(str): string -> int
    if (num == curNum) { result = max(result, stoi(str)); return; }
 
    // 시작 시 n(i)번째부터 시작하여, 재귀함수 호출 시 시간 단축
    for (int i = n; i < str.size() - 1; i++) {
        for (int j = i + 1; j < str.size(); j++) {
            swap(str[i], str[j]);
            dfs(i, curNum + 1); // 현재 교환 횟수를 증가시켜 dfs 재귀 호출
            swap(str[i], str[j]); // 다음 시작점(i)을 위해 문자열 원상 복구
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int C; cin >> C;
    for (int i = 1; i <= C; i++) {
        result = 0;
        cin >> str >> num;
 
        /*
        만약 교환 횟수가 문자열 크기보다 크다면 
        문자열 길이를 넘어가는 교환은 기존 숫자와 동일한 숫자를 얻을 뿐이고
        시간 초과가 날 가능성이 높음(이 부분을 추가했더니 시간초과 안남)
        따라서, 교환 횟수를 문자열 크기 값으로 설정
        */
        if (num > str.size()) num = str.size();
 
        dfs(0, 0);
        cout << "#" << i << " " << result << "\n";
    }
}

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD

SW Expert Academy