트럭 - ACM 2016 문제 중에서

출처 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.
다리건너기 과정

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

입력
입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

출력
출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

샘플 1.

4 2 10
7 4 5 6
8

샘플 2.

1 100 100
10
101

샘플 3.

10 100 100
10 10 10 10 10 10 10 10 10 10
110
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

8개의 풀이가 있습니다.

while __name__ == '__main__':
    #입력
    for s in ['n, w, L', 't']:
        exec(s + ''' = [*map(int, input('>>>').split())]''')
    #다리를 w개의 칸을 가진 리스트로 만듦.
    bridge = [0] * w; end = bridge[:]
    #i를 1부터 세기 시작
    for i in __import__('itertools').count(1):
        #남은 트럭이 있고 다리가 곧 나가는 트럭을 제외한 트럭을 버틸 수 있으면
        if t != [] and sum(bridge[1:]) + t[0] <= L:
            #남은 트럭을 빼서 다리에 트럭 추가
            bridge += [t.pop(0)]
        else:
            #아니면 빈칸 추가
            bridge += [0]
        #한칸 전진
        bridge = bridge[1:]
        #다리가 비어있고 남은 트럭이 없으면
        if bridge == end and t == []:
            #시간을 출력하고 종료
            print(i)
            break

짧은 버전

while __name__ == '__main__':
    for s in ['n, w, L', 't']:
        exec(s + ''' = [*map(int, input('>>>').split())]''')
    bridge = [0] * w; end = bridge[:]
    i = 1
    while True:
        bridge = bridge[1:] + ([t.pop(0)] if t != [] and sum(bridge[1:]) + t[0] <= L else [0])
        if bridge == end and t == []:
            print(i)
            break
        i += 1

파이썬 3.5.2 64

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

#n number of truck
#w bridge length
#l weight
def Cross_the_bridge(n,w,l):
    count,t=0,0
    d_list=[0 for i in range(0,w)]
    c=raw_input().split()
    c_list=[int(i) for i in c] 
    while(len(c_list)!=0):
        count=0
        if(sum(d_list)==0):
            for j in range(0,n+1):
                if(j<=w):
                    if(sum(c_list[0:j])>l):
                        break
            for k in range(0,w):
                if(len(c_list)==0):
                    break
                c_n=c_list.pop(0)
                d_list[count]=c_n
                count+=1
                t+=1

        for i in range(0,w):
            d_list[i]=0
            t+=1
        ##print d_list
        ##print len(c_list)
    print t

Cross_the_bridge(4,2,10)
Cross_the_bridge(1,100,100)               
Cross_the_bridge(10,100,100)   

for문을 이용해서 다리위에 있는 트럭의 무게합이 0일 경우 다리 길이 만큼 무게합이 다리 무게보다 작거나 같을때까지 다리위에 올려 이동시키고 이동할때 마다 시간을 1씩 증가 시키면서 풀었습니다.

  • 입력:4 2 10 결과:8
  • 입력:1 100 100 결과:101
  • 입력:10 100 100 답"110
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def solution(n,w,L,a):
    count = 0
    b = a + [0]
    for i, weight in enumerate(b):
        if b[i] < L and b[i] != 0:
            count += 1
            if b[i+1] < L - b[i]:
                pass
            else:
                count += w-1
        else:
            break
    count = count + w
    return count

Python 3.5.2

입력을 두줄로 하라는 부분은 생략했습니다. 일단 주어진 샘플 입력값들을 넣어보면 다 맞게 나옵니다. 잘못된 부분이 있으면 지적 부탁드립니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
n, w, L = map(int, input(":").strip().split(' '))
an = list(map(int, input(":").strip().split(' ')[:n]))
q = [0] * w
t = 0
for i in an:
    while True:
        t+=1
        q.pop(0)
        if i > L:
            raise Exception('ai <= L')
        elif sum(q)+i > L:
            q.append(0)
        else:
            q.append(i)
            break
while sum(q) != 0:
    t+=1
    q.pop(0)
print(t)

Python 3.5.2에서 작성하였습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
a=input().split(" ")
b=input().split(" ")
if int(a[0])==len(b):
    w=list()
    r=0
    t=0
    for i in range(int(a[1])):
        w.append(0)
    while 1:
        if b.count(0)==len(b) and sum(w)==0:
            break
        if r<int(a[1]):
            w.pop(0)
            if sum(w)+int(b[0])<=int(a[2]):
                w.append(int(b[0]))
                b.pop(0)
                b.append(0)
                t=t+1
                r=r+1
            else:
                w.append(0)
                t=t+1
                r=r+1
        else:
            r=0

    print(t)
else:
    print("잘못된 입력입니다.")
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def bridgetruck(*args):
    x=[list(map(lambda x: int(x), arg.split(" "))) for arg in args]
    a=x[1]; n=x[0][0]; w=x[0][1]; l=x[0][2]; bridge=[0]*w; time=0
    while sum(a)>0:
        if a[0]>w: return "이 화물로는 도저히 다리를 건널 수 없겠는걸?"
        time+=1; bridge.pop(0)
        if sum(bridge)+a[0] < l:
            bridge.append(a.pop(0))
        else: bridge.append(0)
    return time+w

ss=input("다리 정보:" )
sa=input("화물트럭 정보: ")
print(bridgetruck(ss, sa))

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def count_up(val):
    return val+1

data = list(map(int,input().split(' ')))
bus = list(map(int,input().split(' ')))
count, length, weight = 0,0,0
bus2, gps = list(), list()

while bus != [] or bus2 != []:
    count += 1
    if gps != []:
        gps = list(map(count_up,gps))
        if gps[0] == data[1]:
            weight -= bus2.pop(0)
            length -= 1
            gps.pop(0)
    if bus != [] and weight+bus[0] <= data[2] and length < data[1]:
        weight += bus[0]
        length += 1
        gps.append(0)
        bus2.append(bus.pop(0))
print(count)

#### 2017.01.24 D-394 ####
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

move 라는 method를 구현해서, bridge list 와 트럭 list가 한 칸씩 움직일 때마다 사용하는 방법으로 풀어봤습니다. 초보라서 input 받는 부분이 복잡하네요ㅠ

#x = input("input n, w, L and a_n with new line.")
#x = '4 2 10\n7 4 5 6'
#x = '1 100 100\n10'
x ='10 100 100\n10 10 10 10 10 10 10 10 10 10'

def move(list):
    for i in range(len(list)- 1):
            list[i] = list[i+1]
    list[-1] = 0

t = 1
x = x.split('\n')
n, w, L = x[0].split(' ')
a = x[1].split(' ')
a = [int(i) for i in a]
bridge = [0] * int(w)
bridge[-1] = a[0]
move(a)

while 1:
    t += 1
    bridge[0] = 0

    if sum(bridge) + sum(a) == 0:
        break

    elif sum(bridge) + a[0] <= int(L):
        move(bridge)
        bridge[-1] = a[0]
        move(a)

    else:
        move(bridge)

print(t)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 19
기 타 x 2
java x 4
ruby x 1
cpp x 3
javascript x 1
python x 8