[BOJ] 1039 교환 - python

1039번: 교환

1039번: 교환

풀이

처음에 문제를 보고 dfs를 사용하면 되겠군. 했는데 중간에 잘 안풀리자 갑자기 아니 뭐야 greedy로 풀면 되잖아?? 라면서 길을 잘못 들었다. 흠..

다시 생각해보니까 바꾼 것 중에서 최대값이 나오려면 무슨 공식이 있는 것이 아니라 처음부터 끝까지 다 해봐야 한다.

1,000,000 이라는 숫자도 보면 다 해보고 싶게 생긴 숫자다.

#1 . dfs만 사용

1. 문자열의 크기 M의 이중for문을 돌면서 모~~~~~든 경우를 다 돌며
2. answer를 전역변수로 두어 k만큼 수행했을 때 현재까지의 Max를 갱신하도록 하였다.

But, 시간초과 떠버림ㅠㅠ

#2. dfs + dp사용

처음에는 dp테이블을 다음과 같이 생각하였다.

num값과, 몇 번의 k를 했는지를 저장해두면 → 다음에 또 나왔을 때는 반복 작업을 하지 않아도 된다는 것.

dp = [[0 for _ in range(1000000)] for _ in range(K+1)] #num,k (크기 N*K)

따라서 num의 범위가 0<num≤1,000,000이라고 했으므로 안의 배열을 그렇게 설정 해두면 될 줄 알았다.

But, 메모리초과 떠벌임~~~

#3. dfs + dp(dictionary)사용

따라서 각 k에 대해서 num이 몇 개 안 쓰일지도 모르는데 메모리를 차지하고 있는것이 말이 안되기 때문에 등장하는 애들만 dictionary를 이용하여 추가해주기로 하였다.

dp = [{} for _ in range(K+1)] #num,k (크기 N*K)

⇒ 각 최상위 노드에서 max값을 dp테이블에 저장하고 그것을 리턴하는 방식으로 풀이 완료!

 

 

DFS 시간초과 코드

import sys
sys.setrecursionlimit(10**5)

N,K = sys.stdin.readline().rstrip().split(" ")
#print(N,K)
K = int(K)
M = len(N)
#자연수 N을 K번 교환 했을 때 만들 수 있는 가장 큰 수
#0으로 시작하면 안됨 -> 1번째 자리수가 0이면 안됨 (바꿀 때 i,j번째를 바꾼다고 하면 i==0 && num[j]==0이면 못바꿈(넘어가기)

#연산을 K번할 수 없으면 -1 출력 -> 어떤 경우? (-> 두자리인데 두번째 자리수가 0, 한 자리수)
#N<=1,000,000이므로 dfs라는 것을 생각해볼 수 있음. 다 해보기

if (len(N)==2 and N[1]=='0') or len(N)==1:
    print(-1)
    quit()

def swap(tmp,a,b):
    tmp[a], tmp[b] = tmp[b], tmp[a]
    return tmp

answer = 0
#visited는 필요없음(계속 방문가능하니까)
def dfs(num,k):
    global answer
    #종료조건
    if k >= K:
        answer = max(answer,int(''.join(num)))
        return answer

    #if(조건) dfs시행
    for a in range(M):
        for b in range(M):
            if a!=b:
                if a == 0 and num[b] == '0': #0이 맨 앞에 올 수 없음
                    continue
                dfs(swap(num,a,b),k+1)
                swap(num, a, b) #되돌리기
    return

dfs(list(N),0)
print(answer)

dfs + dp(dictionary사용) 코드 (최종)

import sys
sys.setrecursionlimit(10**6)

N,K = sys.stdin.readline().rstrip().split(" ")
#print(N,K)
K = int(K)
M = len(N)
#자연수 N을 K번 교환 했을 때 만들 수 있는 가장 큰 수
#0으로 시작하면 안됨 -> 1번째 자리수가 0이면 안됨 (바꿀 때 i,j번째를 바꾼다고 하면 i==0 && num[j]==0이면 못바꿈(넘어가기)

#연산을 K번할 수 없으면 -1 출력 -> 어떤 경우? (-> 두자리인데 두번째 자리수가 0, 한 자리수)
#N<=1,000,000이므로 dfs라는 것을 생각해볼 수 있음. 다 해보기

dp = [{} for _ in range(K+1)] #num,k (크기 N*K) #num이랑, 몇 번 더 해야 하는지에 최대값 저장해두고 꺼내서 쓰기

if (len(N) == 2 and N[1] == '0') or len(N) == 1:
    print(-1)
    quit()

def swap(tmp,a,b):
    tmp[a], tmp[b] = tmp[b], tmp[a]
    return tmp

#visited는 필요없음(계속 방문가능하니까)
def dfs(num,k):
    #종료조건
    if k >= K:
        return int(''.join(num))
		#dp테이블에 존재하면
    if int(''.join(num)) in dp[k]:
        return dp[k][int(''.join(num))]

    #if(조건) dfs시행
    for a in range(M):
        for b in range(M):
            if a!=b:
                if a == 0 and num[b] == '0': #0이 맨 앞에 올 수 없음
                    continue
                tmp = dfs(swap(num,a,b),k+1)
                swap(num, a, b)  # 되돌리기
                if int(''.join(num)) not in dp[k]:
                    dp[k][int(''.join(num))] = tmp
                else:
                    dp[k][int(''.join(num))] = max(dp[k][int(''.join(num))], tmp)
    return dp[k][int(''.join(num))]

print(dfs(list(N),0))

얻어가는 것

• DFS 안에서 사용하는 값을 변경하게 되면, 다음 가지를 치기 전에 반드시 원상복구 하자!

def dfs(n,num):
	#종료조건

	#dp테이블존재하면

	#가지치기
	for i in range(..):
		dp[n] = **swap(num,a,b)** #값 변경
	**swap(num,a,b)** # 다시 되돌려놓고 다음 가지 gogo

return dp[n] #루트노드 도달

• dp테이블에 dictionary 활용하기

**dp = [{} for _ in range(k)]** #k마다 dictionary 존재, 각 k에 key(인자),value(결과) 넣기

def dfs(num,k):
	#종료조건
	
	#dp테이블존재하면
	**if num in dp[k]:**
		return dp[k][num]

	#가지치기
	for a in range(...):
		**if num not in dp[k]**: #dp테이블에 없으면 새로 생성
			dp[k][num] = tmp(결과값)
		else:
			dp[k][num] = max(dp[k][num],tmp) #dp테이블 값을 활용한 로직
	return dp[k][num]

• dp테이블 2중,3중..n중 배열 생성

#1중
dp = [0 for _ in range(n)] # dp[n]
#2중
dp = [[0 for _ in range(n)] for _ in range(m)] # dp[m]dp[n]
#3중
dp = [[[0 for _ in range(n)] for _ in range(m)] for _ in ragne(l)] # dp[l][m][n]
#...

느낀점

"211006"

소요 시간 : 5H

• dp테이블의 배열 크기가 대따 커질 것 같으면 dictionary를 생각해보자!