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()
ps/problems/boj/28065.txt · 마지막으로 수정됨: 2023/05/29 16:01 저자 teferi
                
                
토론