[Python] 3158번 Sierpinski 삼각형

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

---

 

25/07/30

 

 

약간의 아이디어를 필요로 하는 문제이다.

---

 

문제 접근 방식:

 

 

문제에서 요구하는 것은 T123232232와 같은 형식으로 부분 시어핀스키 삼각형이 문자열로 주어질 때, 해당 부분 시어핀스키 삼각형과 변을 공유하는 모든 부분 시어핀스키 삼각형을 T12323...과 같은 형식으로 출력하는 것이다.

 

먼저 예제 입력에 나와있는 T312를 분석해보자.

그림과 같이 놓여있는 형태이다.

 

T312는 T31이라는 부분 시어핀스키 삼각형에서 2자리에 위치해있다. 따라서, T314와 인접하다는 사실을 알 수 있다.

 

이를 확장시켜보면, 주어지는 문자열이 1, 2, 3으로 끝난다면 해당 문자열의 마지막 글자를 제외한 부분 시어핀스키 삼각형의 4번째 삼각형과 항상 인접함을 알 수 있다.

 

즉, T~~1, T~~2, T~~3꼴의 모든 시어핀스키 삼각형은 T~~4와 항상 인접하다.

 

이후 그림을 보면, T312가 T3이라는 부분 삼각형에서 어느 위치를 차지하는지 생각하는 그림이다.

 

T3이라는 부분 삼각형에 모두 있으므로 12라는 위치가 어디와 인접해있게 되는지 생각해보자.

 

실제로 T34와 인접하는데, 이는 그림에 그려진 것 처럼, 주황색 부분에 해당하는 수많은 작은 부분 시어핀스키 삼각형들이 T34와 인접함을 확인할 수 있다.

 

T312의 경우 T3에서 1의 위치에 있다. 만약 1의 위치에 있다면 주황색 선들에 그려진 것 처럼 이후에 나오는 문자열들은 모두 2나 3으로 구성되어있어야 한다.

 

이를 일반화해보면, T~~1~~에 해당하는 문자열은 1이후에 나오는 문자가 2 또는 3으로만 구성될 때 T~~4와 인접함을 알 수 있다.

 

마찬가지로, T~~2~~에 해당하는 문자열은 2 이후에 나오는 문자가 1 또는 3으로 구성될 때, T~~3~~에 해당하는 문자열은 3이후에 나오는 모든 문자가 1 또는 2로 구성될 때 그러함을 알 수 있다.

 

 

마지막으로, T312는 T4와 인접하는데, 이 또한 마찬가지로 적용할 수 있다. T3 이후의 모든 문자가 1또는 2로만 구성되어있으므로 T4와 인접하게 된다.

 

 

그 외에 만약 T~~4로 끝나는 문자열이면 항상 부분 시어핀스키 삼각형의 중심에 있는 것이므로, T~~1, T~~2, T~~3과 인접함을 알 수 있다.

 

이러한 아이디어를 통해 구현할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 3158번 Sierpinski 삼각형
# 문자열, 애드혹
'''
접근 방법:
일단 T어쩌구하고 4로 끝나면 부분 시어핀스키 삼각형의 한 가운데 있는 것이다.
위, 왼쪽, 오른쪽만 인접하므로, 해당 경우는 T 어쩌구 1, 2, 3만 출력하면 된다.

이후 다음과 같은 로직으로 접근한다.
예제 입력 T312의 경우
T31에서 2의 위치 -> T314와 인접

이후 T31 2~~ 뒷부분을 쭉 보는데
1로 끝나면 뒷부분이 2와 3으로만 이루어져 있어야 T34와 인접한다.
실제로 T312이므로 이건 T34와 인접한다.

T3 12~~~ 뒷부분을 쭉 봄
3으로 끝나면 뒷부분이 1과 2로만 이루어져있어야 T4와 인접
실제로 그러하므로 T4와 인접한다.

T~~1 ---
분리했을 때 1로 끝나고 뒷부분이 2, 3으로만 이뤄져있으면 -> T~~4와 인접

T~~2 ---
2로 끝나고 뒷부분이 1, 3으로만 이뤄져있으면 -> T~~4와 인접

T~~3 --
3으로 끝나고 뒷부분이 1, 2로만 이뤄져있으면 T~~4와 인접
'''
import sys
input = sys.stdin.readline

def solve(test_case_num):
    S = input().rstrip()
    if S[-1] == '4':
        print(S[:-1]+'1')
        print(S[:-1]+'2')
        print(S[:-1]+'3')
        return
    check = [0 for _ in range(3)]
    print(S[:-1]+'4')
    for i in range(len(S)-1, 1, -1):
        now = S[i]
        check[ord(now)-ord('1')] = 1
        before = S[i-1]
        if before == '1':
            if check[0] == 0:
                print(S[:i-1]+'4')
        elif before == '2':
            if check[1] == 0:
                print(S[:i-1]+'4')
        else:
            if check[2] == 0:
                print(S[:i-1]+'4')
    return


def main():
    T = 1
    for i in range(1, T+1):
        solve(i)
    return

main()