[Python, 파이썬] SWEA 22574. 높은 곳으로

모든 N번의 선택이 끝났을 때 당신이 있을 수 있는 가장 높은 층의 번호를 구하는 문제.

 

 

i번째 선택에서, 엘레베이터를 이대로 둘지, 아니면 i층을 올릴지 정할 수 있다.

건물의 P층에는 폭탄이 설치되어 있고 이 층에 멈추면 폭탄이 터진다.

선택이 모두 끝난 후 올라갈 수 있는 가장 높은 층을 구하는 문제.

 

T = int(input()) # 테스트 케이스의 수 T

for test_case in range(1, T+1):

    N, P = map(int, input().split()) # 선택할 수 있는 횟수 N, 폭탄의 위치 P
    answer = 0

    for i in range(1, N+1):

        answer += i # i층 올라가기

        if(answer == P): # 올라간 층이 폭탄이 있는 층이면
            answer -= 1 # 가장 작은 값인 1층 빼주기

    print(answer)

 

 

 

[문제풀이]

---

 

처음엔 DFS, DP 등 고민했는데 생각보다 훨씬 쉬운 문제다.

가장 높이 올라갈 수 있는 층을 구해야 하고, 매 선택마다 i층밖에 올라갈 수 없다.

 

그래서 우선 1부터 N까지 반복문으로 더하는데, 이때 도착한 층이 P층이면 폭탄이 터진다.

if(answer == P): # 올라간 층이 폭탄이 있는 층이면
      answer -= 1 # 가장 작은 값인 1층 빼주기

 

올라간 층이 폭탄이 있는 층일 때, 이전의 층 중 하나를 빼주면 폭탄이 있는 층에 도달하지 않게 된다.

그럼 가장 작은 층 1층을 빼주면 그 층에 도달하지 않고 가장 높이 올라갈 수 있게 된다.

 

이렇게 for문을 모두 돌리면 가장 높이 올라간 층이 나온다!