[백준 / BOJ] 1039 교환

문제

출처 : https://www.acmicpc.net/problem/1039

1039번: 교환

0으로 시작하지않는 정수 N이 주어진다.

정수 N의 자릿수 M에 대해 다음과 같은 연산을 K번 수행했을때, 나올수있는 최댓값을 계산하는 프로그램이다.

 

1 <= i < j <= M 인 i와 j위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

 

소스코드 

BFS로 풀은문제다.

 

우선, BFS로 풀었을때 반복횟수를 계산해보자. N의 자릿수가 최대 9개 이므로 9!, K가 10이므로 

9!*10 이 된다. (중복해서 방문하지않으므로 9!만에 모든숫자들을 찾을수있다.)

 

이때, map구조로 중복을 체크해줬기때문에, 한번 체크하는데 log(N!)정도의 시간이 들고, 최댓값 계산 N의 자릿수만큼의 시간이 들어서, 최종 반복횟수는 

N!*K*(N*log(N!))*N 이 되어서, 최악의 경우에도 약 1억번 반복으로 풀수있다. (체크배열 활용에따라 시간이 더 줄수도 있다.)

 

구현은

 

우선, swap연산을 쉽게하기위해, N을 한자리 한자리 끊어서, vector에 저장했다. 16375 = [1], [6], [3], [7], [5]

 

BFS 수행중 구현을 쉽게하기위해, vector와 현재swap횟수를 담는 queue를 선언했다. (vector에는 위에서 한자리씩끊은 N배열이 들어간다.)

queue<pair<vector<int>,int> > q;

 

중복체크를 해주기위해 map구조를 이용했다. 중복체크는 2차원으로 해줘야하는데, 그 이유가 

N = 13 K = 4 와 같을때

13 -> 31 -> 13 -> 31 과 같은 루트로 이동해 최댓값을 찾을수도 있기때문이다.

따라서, 체크배열을

map<pair<vector<int>,cnt>,int> check;

와 같이 선언한다. (cnt번 이동해서 vector<int> 형태가 되었을때, 이동횟수)

 

위 정보들을 갖고 구현하면된다.

 

-1 출력은

1. N이 한자릿수 인경우

2. N이 두자릿수면서 일의자리가 0인경우 (10의 배수인경우)

 

위 두가지 경우에대해서만 생각해주면된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1039%20%EA%B5%90%ED%99%98/main.cpp

devxb/JJUNalgo