[SWEA 4408] 자기 방으로 돌아가기 (python)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcJ2sapZMDFAV8&categoryId=AWNcJ2sapZMDFAV8&categoryType=CODE&problemTitle=%EC%9E%90%EA%B8%B0+%EB%B0%A9%EC%9C%BC%EB%A1%9C+%EB%8F%8C%EC%95%84%EA%B0%80%EA%B8%B0&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

일단 문제 이해가 너무 어려웠습니다.
고등학생 수련회인데 음주가무를 즐기고,,
분명 친구들과 함께 마셨는데 방은 한 명만 돌아가고..
한 층에 방이 400개나 있는데 바로 앞 방에 가는 시간과 끝에서 끝까지 가는 시간도 같고..
정답을 맞추기까지 한 시간 넘게 걸린 것은 제 탓이 아닙니다.

 

🔥 작성코드 (🌪️60,900kb 174ms)

T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]

    cnt = [0 for _ in range(200)]

    for i in range(N):
        a, b = arr[i][0], arr[i][1]
        if a > b:
            a, b = b, a

        c = a/2
        d = b/2

        if c == int(c):
            c = int(c) - 1
        else:
            c = int(c)

        if d == int(d):
            d = int(d) - 1
        else:
            d = int(d)

        for j in range(c, d+1):
            cnt[j] += 1

    result = 0
    for c in cnt:
        if result < c:
            result = c

    print(f'#{test_case} {result}')

---

 ⭕ 첫 접근법

1.  어떤 방법을 사용해야하나 고민하다가 나가는 친구마다 그 자리에 겹치는 선이 몇 개나 생기는 지 비교했습니다.
2.  그렇다면 그 수만큼 기다렸다가 움직일 수 있다고 생각했습니다.
3.  최종적으로 모든 친구들의 자리에서 겹치는 선의 개수를 센 뒤 가장 큰 수에 1을 더해서 답을 제출했습니다.

결과는 fail .. 애매모호하게 10개 중 8개 통과🤔 그래서 조건문을 만지작거리면서 30분을 넘게 썼습니다.

코드를 천천히 뜯어봤는데 제 생각대로 조건을 구현하는데에는 전혀 문제가 없었습니다.

아 아이디어가 잘 못 됐구나 생각하고 다시 고민했더니 10초도 안되어서 반례가 생각났습니다.

코드 만지기 전에 생각이나 더 해볼걸.. 다시 생각한 방법은 복도 자체에 겹치는 선을 세는 것입니다.

 

💡 다음 접근법

1. 앞서 접근한 방법이 잘못된 경우는 학생은 본인의 자리에 지나간 선이 나갈 수 있는 순서가 되는 것은 아닙니다.
2. 겹쳐있는 경우, 같은 3,3 이라도 앞의 3이 나가야 뒤의 3도 나갈 수 있기 때문에 최소 5이상의 시간이 필요합니다.
3. 하지만 복도에 겹친 선의 개수는 시간마다 하나씩 지워질 수 있으므로 이 값을 통해 답을 구할 수 있습니다.
4. 복도는 1,2사이에 하나씩 있다고 가정하고 복도의 길이를 200으로 잡았습니다.
5. 학생이 출발하는 방과 도착하는 방 중 작은 값을 a, 큰 값을 b로 초기화 시켰습니다.
6. 그리고 a부터 b까지 가는 길을  포함하는 복도에 +1을 해주었습니다.
7. 이것을 모든 학생들에 대해 반복했습니다.
8. cnt에 저장된 가장 큰 값을 찾았습니다.
   • 만약 1 => 3, 5 =>2 번 방으로 이동하는 두 학생이 있다하면 복도에 저장되는 값

1	3	5	7	...	...	...	395	397	399
2	2	1	0	복도			0	0	0
2	4	6	8	...	...	...	396	398	400