글 읽기 - 이렇게 풀면 해결이 되지 않는걸까요?

devacver 2년 전 0

덱으로 짜보려다 로직상 아래 코드와 같이 해도 풀려야 되지 않나 싶어서 해봤는데

3, 4번 예제가 1씩 오차가 발생하네요 어디서 문제가 생긴걸까요?

n, m = map(int, input().split())
rm = list(map(int, input().split()))

add = 0
sub = 0
pop = 0
for i in rm:

    i += add - sub - pop
    if i > n:
        i %= n
    while i < 1:
        i += n
    if i == 1:
        pop += 1
        n -= 1
    elif i > n/2:
        add += n - i + 1
        pop += 1
        n -= 1
    else:
        sub += i - 1
        pop += 1
        n -= 1
    
print(add+sub)

zenith82114 2년 전 0

반례입니다.

왼쪽 이동 1번만 하면 되는 경우입니다.

3 3
2 3 1

// ans: 1
// out: 3

devacver 2년 전 0

위 코드와 같이 다시 수정했는데 어떤 부분에서 수식 연산이 잘못 됐는지 혹시 봐주실 수 있으실까요?

add = 0
sub = 0
pop = 0

for i in rm:
    i += add - sub - pop-1
    if i > n-1:
        i %= n
    while i < 0:
        i += n
        
    if i == 0:
        pop += 1
        n -= 1
    elif i > n/2:
        add += n - i
        pop += 1
        n -= 1
    else:
        sub += i
        pop += 1
        n -= 1
    print(n, i, add, sub)
        
print(add+sub)

zenith82114 2년 전 1

i값을 수정하는 게 지금 꺼내야 하는 원소가 가 있는 실제 인덱스를 계산하시려는 거 같은데,

꺼낸 원소들(또는 순서)을 모두 저장해 놓지 않는 한 불가능할 것 같습니다.

아래의 case A, B에서 마지막에 1을 꺼내기 전까지는 add 3번 sub 2번 pop 2번으로 똑같고

add랑 sub 중에 어느 게 먼저였냐만 다른데 마지막에 1이 가 있는 인덱스는 A, B에서 서로 다릅니다.

즉 add, sub, pop의 순서 없이 횟수만 가지고는 덱의 상태를 복원할 수 없습니다.

// case A
7 3
4 2 1
// [1 2 3 4 5 6 7]
// [5 6 7 1 2 3] (<- 3)
// [3 5 6 7 1]   (-> 2)
// [3 5 6 7]     (-> 1)

// case B
7 3
6 3 1
// [1 2 3 4 5 6 7]
// [7 1 2 3 4 5] (-> 2)
// [4 5 7 1 2]   (<- 3)
// [2 4 5 7]     (-> 2)

devacver 2년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이렇게 풀면 해결이 되지 않는걸까요?

devacver 2년 전 0

zenith82114 2년 전 0

devacver 2년 전 0

zenith82114 2년 전 1

devacver 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말