개발 공부/알고리즘 문제풀이

[백준] 10250. ACM 호텔

5묘 2022. 7. 25. 23:55
 

10250번: ACM 호텔

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수

www.acmicpc.net


이 문제는 쉽게 접근해서 풀었지만, 중간에 미처 찾지 못한 반례때문에 계속 틀리다가 반례를 알아내서 맞춘 문제이다.

처음에는 이렇게 flag 없이 풀었다.

# 10250 ACM호텔

T = int(input())

for tc in range(1, T+1):
    H, W, N = map(int, input().split())
    cnt = 1

    for w in range(1, W+1):
        for h in range(1, H+1):
            if cnt == N:
                print(str(h*100 + w))
                break
            else:
                cnt += 1
        if cnt == N:
            break

그랬더니 계속 틀려서 대체 내가 놓친 반례가 뭔지 백준 질문게시판을 뒤져보았다.
그랬더니 아뿔싸, 'H=38, W=10, N=39'인 경우에 출력이 안되는 문제가 있었다.

왜 그런가 봤더니 반복문에서 N=39일 때, H의 모든 열을 한바퀴 다 돌고 나면 안의 반복문에서는 아직 N이 38이라 break가 되지 않는데, w가 1 증가하게 되는 밖의 반복문에서 cnt==N을 만족해버려서 break로 반복문을 나가버리고, 아무것도 출력되지 않는 문제였다. 

그래서 내부 반복문의 break가 실행되어야만 밖의 반복문도 break가 걸리도록 flag를 추가해두었다.

# 10250 ACM호텔

T = int(input())

for tc in range(1, T+1):
    H, W, N = map(int, input().split())
    cnt = 1
    flag = False

    for w in range(1, W+1):
        for h in range(1, H+1):
            if cnt == N:
                print(h*100 + w)
                flag = True
                break
            else:
                cnt += 1
        if cnt == N and flag == True:
            break

이렇게 했더니 무사히 통과~!


나는 이중 반복문을 사용해서 다소 복잡하고 시간이 많이 걸렸다.(반례 하나하나를 생각해야 했고)
다른 분들이 푸신 방법을 보니까 손님이 방문한 순서 N과 객실 호수 사이의 규칙성을 찾아내서, 층수는 N에서 건물 층수 H를 나눈 나머지로, 호수는 층수로 나눈 몫 + 1로 푸신 경우가 있었다! (이게 더 간단해보인다)

참고: https://ooyoung.tistory.com/88

 

백준 10250 [파이썬 알고리즘] ACM 호텔

[Python] 백준 알고리즘 온라인 저지 10250번 : ACM 호텔 Python3 코드 t = int(input()) for i in range(t): h, w, n = map(int, input().split()) num = n//h + 1 floor = n % h if n % h == 0: # h의 배수..

ooyoung.tistory.com