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
토론