백준 2469 사다리 타기

2010 정보올림피아드 초등부 마지막 문제이다.

문제 풀이

1. A부터 순서대로 k개의 알파벳의 배열을 만든다.

2. ?로 시작하는 사다리가 나올 때 까지 1에서 만든 배열을 주어진 사다리에 따라 바꾸어 나간다.

3. ?로 시작하는 사다리를 만나면 그 이후의 사다리들을 배열에 넣고 뒤집어 준다.

4. 정답 배열을 3의 배열에서 순서대로 꺼내며 사다리에 맞게 정답 배열을 바꾸어 나간다.(3에서 뒤집에 주었으므로 정답 배열은 가장 밑의 사다리부터 따라가게 된다.)

5. 1의 배열과 4의 배열을 비교하여 적절한 사다리 모양을 만든다.

 

Python Code

import string, sys
al = string.ascii_uppercase
k=int(sys.stdin.readline())
n=int(sys.stdin.readline())
al = list(al[:k])
answer = list(sys.stdin.readline()[:-1])
def swap(i):
    temp = al[i]
    al[i] = al[i+1]
    al[i+1] = temp
 
def swap2(i):
    temp = answer[i]
    answer[i] = answer[i+1]
    answer[i+1] = temp
 
for i in range(n):
    ladder = sys.stdin.readline().split()[0]
    if ladder[0] == "?":
        break
    else:
        for idx,l in enumerate(ladder):
            if l =="-":
                swap(idx)
 
rest = [sys.stdin.readline().split()[0] for _ in range(i+1,n)]
rest.reverse()
for ladder in rest:
    for idx,l in enumerate(ladder):
        if l =="-":
            swap2(idx)
ans = ""
 
for i in range(k-1):
    if al[i] == answer[i]:
        ans += "*"
    elif al[i] == answer[i+1] and al[i+1]==answer[i] and (i==0 or ans[-1] == "*"):
        ans += "-"
        swap(i)
    else:
        ans = "x" * (k-1)
        break
print(ans)

line 5의 al이 과정 1의 배열이다.

line 6의 answer가 과정4의 정답 배열이다.

swap 함수는 al을 사다리에 따라 바꿔주며, swap2는 answer를 바꿔준다.

line 17의 for 문이 과정 2이며, line26의 rest배열이 과정 3의 ?이후의 사다리 배열이다.

line 28의 for 문이 과정 4이다.

line 34가 마지막 과정 5 이다.

37 line의 마지막 조건의 경우, 사다리가 연속으로 이어진 경우는 없다는 조건을 구현한 것이다.

 

문제 링크

2469번: 사다리 타기