[백준 2579] 계단 오르기 풀이노트

위 로고를 누르면 해당 문제로 이동합니다.

1차 풀이 (2018-08-04, 1984 KB, 0 MS)

1칸으로 2번 시도하면 안된다. (1)

처음 계단을 올라갈 때를 제외하고는 1칸으로 2번 연속 시도하면 안된다.

연속한 3개의 계단을 밟을 수 없다는 룰 때문이다.

0	1	2	3

0에서 시작했을 경우 ) 0, 1, 2 → 연속되는 계단 2개로 규칙위반 아님.

1에서 시작했을 경우 ) 1, 2, 3 → 연속되는 계단 3개로 규칙위반.

0에서 시작한 경우를 먼저 처리하고,

이후로는 1칸을 2번 시도하지 않으면서 차근차근 계단을 건너본다.

1칸으로 2번 시도하면 안된다. (2)

1칸을 2번 시도하지 않는다는 것은,

1칸을 시도한 차례의 전후는 항상 2칸으로 시도해야 한다는 것을 의미한다.

→ 1칸을 시도한 후에는 반드시 2칸을 시도하도록 강제하는 규칙을 사용한다.

→ 위의 규칙을 강제함으로써 1칸의 전후는 항상 2칸으로만 시도된다.

따라서 계단을 올라가는 방법은 2개로 좁혀진다.

1) 2칸 올라가기.

2) 1칸 2칸 올라가기.

계단 수가 적은 케이스는 미리 처리하자.

계단의 수가 3칸 이하인 경우는 미리 처리하여 알고리즘의 예외를 없앤다.