사용자 도구

사이트 도구


ps:problems:boj:28065

SW 수열 구하기

ps
링크acmicpc.net/…
출처BOJ
문제 번호28065
문제명SW 수열 구하기
레벨실버 4
분류

애드혹

시간복잡도O(n)
인풋사이즈n<=5000
사용한 언어Python 3.11
제출기록31256KB / 44ms
최고기록44ms
해결날짜2023/05/29

풀이

  • 길이가 N인 SW수열에서, 인접한 원소의 차이로 이루어진 수열을 만들면 길이는 N-1이다
  • SW수열은 1이상 N이하의 수로 만들어져 있으므로, 두 수의 차의 최댓값은 N-1, 최솟값은 1이다.
  • 두 사실을 조합하면, 인접한 원소의 차이로 이루어진 수열은 N-1,N-2,…,1 이 되어야 한다.
  • 이것을 만족하는 수열을 만들어보자. 첫 두항의 차가 N-1이면, 처음 두 수는 1,N 이거나 N,1 이어야만 한다
  • 1,N 으로 시작했을 경우, 그 이후에 인접한 항의 차가 N-2,N-3,… 이 되게 하려면 수열은 1,N,2,N-1,3,N-2, … 이렇게 이어져야 한다.
    • N,1로 시작했을 경우는 N,1,N-1,2,N-3,3, … 이다
  • 둘중에서 아무거나 출력하면 된다.
  • 사실, 이런 추론과정을 걸치지 않더라도, 이것이 대충 답이 될만하다고 떠올리고 이것이 진짜로 조건을 만족시킨다는 것을 증명하는 것은 어렵지 않다. 이 추론과정은 답이 이렇게 두가지밖에 존재하지 않는다는 것을 보이는데에 더 도움이 되는 느낌.
  • 시간복잡도는 O(n)

코드

"""Solution code for "BOJ 28065. SW 수열 구하기".

- Problem link: https://www.acmicpc.net/problem/28065
- Solution link: http://www.teferi.net/ps/problems/boj/28065

Tags: [Ad hoc]
"""


def main():
    N = int(input())

    answer = [None] * N
    answer[::2] = range(1, (N + 1) // 2 + 1)
    answer[1::2] = range(N, (N + 1) // 2, -1)

    print(*answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
U D C L B
 
ps/problems/boj/28065.txt · 마지막으로 수정됨: 2023/05/29 16:01 저자 teferi