백준 29793: 라라와 용맥 변환 (Python)

문제링크

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

문제 총평

- 문제 유형을 안다면 매우 쉽게 풀 수 있다.

문제 접근방식

- 이번 문제는 처음에는 굉장히 당황스럽던 문제이지만 문제 풀이법을 알고 나면 아주 쉬웠던 문제였습니다.

- + 파이써닉 하게 아주 쉽게 풀 수 있습니다

정답코드

import sys;input = sys.stdin.readline
n,m = map(int,input().split())
arr = list(input())
ans = 987654321
if m == 1: print(0)
elif m == 2:
    ans = 0
    for i in range(1,n):
        if arr[i] == arr[i-1]:
            ans +=1
            arr[i] = 0
    print(ans)
elif m == 3:
    lst = [list("SRW") * (n//3+1),list("RWS")  * (n//3+1),list("WSR") * (n//3+1),
     list("WRS") * (n//3+1),list("RSW") * (n//3+1),list("SWR") * (n//3+1)]
    for j in lst:
        tem = 0
        for i in range(n):
            if arr[i] != j[i] : tem +=1
        ans = min(ans,tem)
    print(ans)
else:
    if n < 4:
        lst = [list("SRW") * (n//3+1),list("RWS")  * (n//3+1),list("WSR") * (n//3+1),
     list("WRS") * (n//3+1),list("RSW") * (n//3+1),list("SWR") * (n//3+1)]
        for i in lst:
            tem = 0
            for j in range(n):
                if arr[j] != i[j] : tem +=1
            ans = min(ans,tem)
        print(ans)
    else: print(-1)

1. 이 문제는 많은 조건 분기와 브루트 포스로 쉽게 풀 수 있습니다.
2. 생각을 해보면, m = 1, m = 2, m = 3, m = 4 이상 일때로 나눠서 생각할 수 잇습니다
3. m = 1일때를 생각해보면 어떤 경우에서든, 어떤 것도 바꾸지 않고 진행할 수 있으므로 0을 출력합니다.
4. m = 2 일때는 바로 앞에 용맥과 현재 용맥이 다르기만 하면 되기 때문에 앞과 비교하면서 다르면 ans += 1을 해줍니다.
5. m = 3 일때부터는 다르게 생각을 해야 하는데, 생각을 해보면 m이 3인 경우는 S R W 가 계속 반복되거나, S W R이 계속 반복되거나 ... 이렇게 6가지 경우 밖에 없으므로 모든 경우를 다 완전 탐색으로 얼마나 차이가 나는지만 확인 해보면 됩니다. (저는 경우가 6가지 밖에 없기 때문에 모든 경우를 만들어서 햇지만 파이썬으로는 permutation으로 쉽게 모든 경우를 만들 수 있습니다.
6. m = 4일때 부터는 n을 생각해야하는데, 먼저 n > 3인 경우는 모두 불가능 하기 때문에 -1을 출력하고 n <4 인경우는 모든 용맥이 다르면되므로 5번에서 사용한 리스트를 다시 가져와서 차이의 최솟값을 출력하면 됩니다. 

문제 풀이 후 생각

- 개인적으로는 골드 3이라는 난이도를 보고 좀 쫄앗지만 풀이를 알고 나서는 아주 쉬운문제가 되므로 골드 4정도의 문제가 아닌가 싶습니다.

 + 

- Python이 아닌 경우에는 주어진 용맥의 맨 앞 3개의 용맥을 보고 1. 3개의 용맥이 전부 다른지 체크한다. 2. 그 뒤의 용맥들이 맨 앞의 3개의 용맥의 순서와 같은가? 를 보고 풀이하면 됩니다. 

 

모르는게 있다면 댓글 또는 godzz733@naver.com으로 메일 남겨 주세요