[SWEA][D4] 4408. 자기방으로 돌아가기 D4 파이썬

문제출처 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcJ2sapZMDFAV8

4408. 자기 방으로 돌아가기 D4 파이썬

 

고등학교 학생들이 학교에서 수련회를 갔다. 수련회에 간 학생들은 친구들과 음주가무를 즐기다가 밤 12시가 되자 조교들의 눈을 피해 자기방으로 돌아가려고 한다.

제 시간에 자기방으로 돌아가지 못한 학생이 한 명이라도 발견되면 큰일나기 때문에 최단 시간에 모든 학생이 자신의 방으로 돌아가려고 한다.

숙소는 긴 복도를 따라 총 400개의 방이 다음과 같이 배열되어 있다.

 

모든 학생들은 현재 위치에서 자신의 방으로 돌아가려고 하는데, 만약 두 학생이 자기방으로 돌아가면서 지나는 복도의 구간이 겹치면 두 학생은 동시에 돌아갈 수 없다.

예를 들어 (방1 -> 4) 와 (방3 -> 6) 은 복도 구간이 겹치므로 한 사람은 기다렸다가 다음 차례에 이동해야 한다. 이동하는 데에는 거리에 관계없이 단위 시간이 걸린다고 하자.

각 학생들의 현재 방 위치와 돌아가야 할 방의 위치의 목록이 주어질 때, 최소 몇 단위시간만에 모든 학생들이 이동할 수 있는지를 구하시오.


[입력]
입력은 T(≤10)개의 테스트 케이스로 되어 있다. 각 테스트 케이스의 첫 줄에는 돌아가야 할 학생들의 수 N이 주어진다.

다음 N 줄에는 각 학생의 현재 방 번호(≤400)와 돌아가야 할 방의 번호(≤400)가 주어진다.

주어지는 2N개의 방 번호 중 중복되는 것은 없다.

[출력]
테스트 케이스 T에 대한 결과는 “#T ”을 찍고, 각 테스트 케이스마다 필요한 시간을 한 줄에 하나씩 출력한다.

 

 

<PASS>

# 2020.03.10
# 4408. 자기방으로 돌아가기 D4 파이썬
 
# 실패1..10개중2개맞음 - 0~400번까지의 방을 한 줄로 해서 겹치는 부분을 리턴하자..
# 실패2..10개중9개맞음 - 방 번호가 큰 수에서-> 작은 수로 가는 경우 고려
# 시도3.. 끝이 홀수이면 +1에도 영향, 앞이 짝수면 -1 방에도 영향을 미친다. 
# [1,3][4,6] 이라면 3,4가 복도에서 만나서 최종값이 2 가 될 수 있음. 복도를 중심으로 바꿈
 
for tc in range(1,int(input())+1):
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(n)]
    temarr = [0 for i in range(201)] # 0~200번까지 복도 만들기
    for m in arr: # 한 명당 방이동 하자
        # temarr[arr[x][0]:arr[x][1]+1] 값에 1 씩 증가
        if m[0] < m[1]:
            start = (m[0]+1)//2
            end = (m[1]+1)//2
        else:
            start = (m[1]+1)//2
            end = (m[0]+1)//2         
        for i in range(start,end+1):
            temarr[i] += 1
    #print(temarr)
    print(f'#{tc} {max(temarr)}')
 
 

 

 

0~400번까지의 방을 한 줄로 해서 겹치는 부분을 리턴하자..

실패1..10개중2개맞음 

 

방 번호가 큰 수에서-> 작은 수로 가는 경우 고려

실패2..10개중9개맞음 - 크읍

 

 

# 2020.03.10
# 4408. 자기방으로 돌아가기 D4 파이썬 (실패)
 
# 실패1..10개중2개맞음 - 0~400번까지의 방을 한 줄로 해서 겹치는 부분을 리턴하자..
# 실패2..10개중9개맞음 - 방 번호가 큰 수에서-> 작은 수로 가는 경우 고려
 
for tc in range(1,int(input())+1):
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(n)]
    temarr = [0 for i in range(401)] # 0~400번까지 방 만들기
    for m in arr: 
        if m[0] < m[1]:
            start = m[0]
            end = m[1]
        else:
            start = m[1]
            end = m[0]            
        for i in range(start,end+1):
            temarr[i] += 1
    print(f'#{tc} {max(temarr)}')
 

 

시도3.. 끝이 홀수이면 +1에도 영향, 앞이 짝수면 -1 방에도 영향을 미친다. 

[1,3][4,6] 이라면 3,4가 복도에서 만나서 최종값이 2 가 될 수 있음. 내가 만든 코드로는 1이 됨. 

홀수일 때, 짝수일 때 고려하기 보다는 ..

0~200번까지의 복도를 만들어서 양쪽 방과의 연관성을 봤을 때, 

(x방번호+1) // 2 = 복도번호 가 되는 것을 이용하여 수정 완성