[호붕싸 모각코 2주차] 실전프로젝트 문제 다시풀기

작성자	김윤희
소 감	오늘은 실전프로젝트 수업에서 진행한 알고리즘 문제를 다시 푸는 시간을 가졌다. 금요일에 모각코를 하는 건 좋은것 같다. 실프에서 놓쳤거나 시간안에 해결하지 못한 문제를 다시 풀 수 있는 시간을 가질 수 있기 때문에!
일 시	2025. 3. 14. (금) 18:00 ~ 21:00
장 소	미래관 429호 자율주행스튜디오
참가자 명단	신수민, 임혜진, 배세은, 김윤희 (총 4명)
사 진

 

계단 오르기

<문제 설명>

계단을 오를 때, 한 번에 최대 2칸씩 올라갈 수 있으며, 계단 중간에 망가진 계단이 있는 경우 그 부분은 안전을 위해 넘어가야 한다. 

총 계단 수 n과 망가진 계단의 위치 p가 주어졌을 때, 끝까지 올라가는데 필요한 최소 걸음 수를 return 해야한다. 

 

문제를 보고 dp로 풀어야겠다고 생각했는데, 알고보니 dp로 풀지 않아도 충분히 풀 수 있었던 문제였다. 

먼저 내 풀이는 아래와 같다. 

def stair(n, p):
    dp = [float('inf')] * (n+1)
    
    dp[0] = 0 
    
    for i in range(1, n+1):
        if p == i:
            continue
        print(dp)
        step1 = dp[i-1] 
        step2 = dp[i-2]
        dp[i] = min(step1, step2) + 1
        
    return dp[n]

t = int(input())

for i in range(t):
    n, p = map(int, input().split())
    print(stair(n, p))​

 

망가진 계단 p가 i와 같을 때 건너뛰면서 1번 부터 n번 까지 순차적으로 최소 이동 횟수를 갱신하며 dp 테이블을 채우게 된다. 

 

하지만 "최소"를 생각해 보았을 때, 

n이 짝수인 경우에는 무조건 두칸 씩 올라가는 것, n이 홀수인 경우에는 두 칸씩 올라간 후 마지막 한 칸을 더하는게 항상 최소가 된다. 

 

그렇다면 p를 고려해 보자.

망가진 계단이 홀수에 위치해있다면 고려하지 않고 두 칸씩 올라가면 된다. 

하지만 망가진 계단이 짝수라면 0 에서부터 시작하지 않고, 한 칸 더한 후 1 에서부터 시작한 후 두 칸씩 오르면 된다. 

 

위와 같은 방식으로 dp를 이용하지 않고 구현의 맥락에서 해당 문제를 해결할 수 있었다. 

 

하지만 위 코드를 조금 개선하자면, 

dp[i-1] 이나 dp[i-2]를 참조할 때 0보다 작아지는 경우가 발생할 수 있으므로 조건문으로 걸어주는 것이 오류를 방지할 수 있을 것이다. 

또한 p 번째 계단을 건너뛸 때, dp[i]를 갱신하지 않으므로 나중에 참조할  때 문제가 발생할 수 있을 것을 대비하는 것도 좋아보인다. 

 

def stair(n, p):
    if n == p:  # 마지막 계단이 막혀 있으면 도달 불가능
        return -1
    
    dp = [float('inf')] * (n+1)
    
    dp[0] = 0  # 시작점
    
    for i in range(1, n+1):
        if i == p:  # 금지된 계단은 건너뛴다
            continue
        
        if i - 1 >= 0 and dp[i-1] != float('inf'):  # 한 계단 전에서 올 수 있는 경우
            dp[i] = min(dp[i], dp[i-1] + 1)
        
        if i - 2 >= 0 and dp[i-2] != float('inf'):  # 두 계단 전에서 올 수 있는 경우
            dp[i] = min(dp[i], dp[i-2] + 1)
    
    return dp[n] if dp[n] != float('inf') else -1  # 도달 가능하면 최소 횟수, 아니면 -1 반환

t = int(input())

for _ in range(t):
    n, p = map(int, input().split())
    print(stair(n, p))

 

위는 수정된 코드이다. 

---