코-다시풀기-흥-2주차

다리를 지나는 트럭

1. que 미리 bridge_length 만큼 생성
2. truck_weights[0] + sum (que) <= weight로 트럭 지나갈 수 있는지 여부 확인
3. 지나갈 수 없다면, que에 0 append
4. 지나갈 수 있다면 truck 배열에서 pop 해서 que에 push
5. que가 null이 될 때까지 반복

def main():
    print(solution(2,10,[7,4,5,6]))

def solution(bridge_length, weight, truck_weights):
    answer = 0
    que = [0 for _  in range(bridge_length)]
    while(que):
        que.pop(0)
        answer+=1

        if truck_weights:
            if truck_weights[0] + sum(que) <= weight:
                t = truck_weights.pop(0)
                que.append(t)
            else : que.append(0)
        
    return answer
    
if __name__ == "__main__":
    main()

정수 삼각형

맨 왼쪽, 맨 오른쪽, 가운데 이렇게 3가지로 나눠서 생각.
1. 맨 왼쪽일 경우 dp[i-1][j] 의 값 이용
2. 맨 오른쪽 일경우 dp[i-1][j-1] 값 이용
3. 가운데 일 경우 max(dp[i-1][j],dp[i-1][j-1]) 값 이용
4. 모든 triangle 값 순회하면서 max 값 갱신.
5. 최대 max 값 리턴

def main():
    print(solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]))

def solution(triangle):
    answer = 0
    n = len(triangle)
    dp=[[0 for j in range(n)] for i in range(n)]
    dp[0][0] = triangle[0][0]

    for i in range(n):
        for j in range(i):
            if j==0:
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            elif j==i:
                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
            else:
                dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]

            answer = max(answer,dp[i][j])
    return answer
    
if __name__ == "__main__":
    main()
### 주식가격
> 원래 스택/큐 문제인데 그냥 완전탐색으로 가능.

```python
def main():
    print(solution([1, 2, 3, 2, 3]))

def solution(prices):
    answer = [0 for _ in range(len(prices))]
    for i in range(len(prices)):
        for j in range(i+1,len(prices)):
            answer[i] += 1
            if prices[i] > prices[j]: 
                break
            # else: continue
    return answer

if __name__ == "__main__":
    main()

주식 가격

스택/큐 로 분류되어있지만 완전탐색으로 가능

def main():
    print(solution([1, 2, 3, 2, 3]))

def solution(prices):
    answer = [0 for _ in range(len(prices))]
    for i in range(len(prices)):
        for j in range(i+1,len(prices)):
            answer[i] += 1
            if prices[i] > prices[j]: 
                break
            # else: continue
    return answer

if __name__ == "__main__":
    main()