[swea] 5293번: 이진 문자열 복원 - 파이썬(python)

DFS 로 풀었다가 시간초과로 낭패를 본 문제..

무작정 문제를 보자마자 달려들지 말고, 천천히 규칙을 찾아보는 습관을 가지자.

 

 

꼭 알아야 할 규칙은, 01패턴과 10패턴은 항상 개수가 같거나, 혹은 개수 차이가 1이라는 것이다.

위 규칙만 안다면, 아래 코드를 쉽게 구현할 수 있을 것이다.

 

<규칙>

a : 00패턴의 개수

b : 01패턴의 개수

c : 10패턴의 개수

d : 11패턴의 개수

 

1. <00 패턴만 존재하는 경우>

"0" * (a+1)

2. <11 패턴만 존재하는 경우>

"1" * (d+1)

3. <b==c 이면서 b,c 값이 1이상인 경우>

"0" * (a+1) + "10" * (b-1) + "1" * (d+1) + "0"

4. <b-c 의 값이 1인 경우>

"0" * (a+1) + "10" * (b-1) + "1" * (d+1)

5. <c-b 의 값이 1인 경우>

"1" * (d+1) + "01" * b + "0" * (a+1)

6. 나머지의 경우는 존재할 수 없다.

10패턴이 n번 나타나면 어떠한 경우에도 01패턴이 n-1번, n번, n+1 번으로 나타나기 때문이다. 즉, 01과 10의 차이값은 항상 1이하여야 한다.

 

 

 

나의 풀이

T = int(input())
answer = []
for t in range(1, T+1):
    a, b, c, d = list(map(int, input().split()))
    if a and not b and not c and not d:
        result = "0" * (a+1)
    elif d and not a and not b and not c:
        result = "1" * (d+1)
    elif b == c and b:
        result = "0" * (a+1) + "10" * (b-1) + "1" * (d+1) + "0"
    elif b-c == 1:
        result = "0" * (a+1) + "10" * (b-1) + "1" * (d+1)
    elif c-b == 1:
        result = "1" * (d+1) + "01" * b + "0" * (a+1)
    else:
        result = "impossible"

    answer.append(f'#{t} {result}')

print(*answer, sep='\n')