1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

N = int(input())
wine = [0 for _ in range(N)]
total = [0 for _ in range(N)]

for i in range(N):
    wine[i] = int(input())

if N == 1:
    total[0] = wine[0]
else:
    total[0] = wine[0]
    total[1] = wine[0] + wine[1]

for i in range(2, N):
    total[i] = max(total[i-1], total[i-2] + wine[i], total[i-3] + wine[i] + wine[i-1])

print(total[N-1])

# N == 1인 경우를 생각하지 않았을 땐 런타임 오류에 걸렸었다.
# 그리고 그걸 생각하는데 오래 걸렸다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import sys

N = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().split()))

result = [arr[0]]
for i in range(N-1):
    result.append(max(result[i]+arr[i+1], arr[i+1]))

print(max(result))

# dp 연습하기 좋은 문제

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

def w(a,b,c):

    if a <= 0 or b <= 0 or c <= 0:
        return 1

    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)

    if dp[a][b][c]:
        return dp[a][b][c]
    
    if a < b and b < c:
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) 
        return dp[a][b][c]

    dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)   
    return dp[a][b][c]

dp = [[[0]*21 for _ in range(21)] for _ in range(21)]

while True:
    a, b, c = map(int, input().split())

    if a == -1 and b == -1 and c == -1:
        break

    print(f'w({a}, {b}, {c}) = {w(a, b, c)}')

# 갑자기 난이도가 높아진듯..
# 3차원 dp까지는 어찌저찌 고안했으나
#     if dp[a][b][c]:
#         return dp[a][b][c]
# 를 어디에 넣어야 할지 고민하는데 
# 시간을 소요.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

for T in range(int(input())):
    S = " " + input()
    L = len(S)
    result = 1
    for i in range(2, L):
        for j in range(L-i):
            if S[j+1:j+i+1] == S[j+i:j:-1]:
                result = i

    print(f'#{T+1} {result}')
    
# 슬라이싱을 잘 고민 하면 쉽게 해결

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

for T in range(int(input())):
    q = []
    n = ""
    for N in range(int(input())):
        q.append(input())

    S = 0
    L = N

    while S != L:
        if q[S] < q[L]:
            n += q[S]
            S += 1
        elif q[S] > q[L]:
            n += q[L]
            L -= 1
        else:
            W = int((L-S)//2)
            for i in range(W):
                flag = True
                c = q[S+i+1]
                d = q[L-(i+1)]
                if c == d:
                    continue
                elif c < d:
                    n += q[S]
                    S += 1
                    flag = False
                    break
                elif c > d:
                    n += q[L]
                    L -= 1
                    flag = False
                    break
            if flag:
                n += q[S]
                S += 1
    n += q[L]

    print(f'#{T+1} {n}')

# 조건은 다 쉬웠으나, 검사하는 횟수?에 착각을해
# 생각보다 시간이 많이 걸린 문제

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

from collections import deque

for T in range(int(input())):
    command = deque(input().split())
    N = command.popleft()
    
    B = deque()
    O = deque()
    order = deque()
    while command:
        i = command.popleft()
        if i == "B":
            B.append(int(command.popleft()))
            order.append("B")
        else:
            O.append(int(command.popleft()))
            order.append("O")

    count = 0
    b, o = 1, 1
    while True:
        if not order:
            break
        count += 1

        BP = "안눌림"
        if B:
            if B[0] > b:
                b += 1
            elif B[0] == b and order[0] == "B":
                B.popleft()
                order.popleft()
                BP = "눌림"
            elif B[0] < b:
                b -= 1
        
        if O:
            if O[0] > o:
                o += 1
            elif O[0] == o and order[0] == "O" and BP == "안눌림":
                O.popleft()
                order.popleft()
            elif O[0] < o:
                o -= 1

    print(f'#{T+1} {count}')


# 주어진 순서대로 버튼을 눌러야 한다!!!
# 첫번째 테스트의 경우 O에 1이 있으나, B2가 눌리기를 기다려야 한다.
# order 리스트가 필요한 이유

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import sys
from collections import deque

def isSafe(x, y):
    if 0 <= x < N and 0 <= y < M:
        return True

def BFS():
    while q:
        x, y = q.popleft()
        visited[x][y] = 1
        for i in range(4):
            cx = x + dx[i]
            cy = y + dy[i]
            if isSafe(cx, cy) and arr[cx][cy] == 1 and visited[cx][cy] == 0:
                q.append([cx, cy])
                arr[cx][cy] = arr[x][y] + 1
    

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

N, M = map(int, sys.stdin.readline().split())

arr = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]
visited = [[0]*(M) for _ in range(N)]
q = deque([[0, 0]])

BFS()

print(arr[N-1][M-1])


# pop을 사용하는데 리스트형태의 자료인 경우
# x, y = [1, 2]의 모습으로도 추출이 가능

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import sys
from collections import deque

def DFS(V):
    print(V, end=' ')
    DFSv[V] = 1
    for i in range(1, N+1):
        if DFSv[i] == 0 and tree[V][i] == 1:
            DFS(i)
    return


def BFS(V):
    q = deque([V])
    BFSv[V] = 1
    while q:
        p = q.popleft()
        print(p, end=" ")
        for i in range(1, N+1):
            if BFSv[i] == 0 and tree[p][i] == 1:
                q.append(i)
                BFSv[i] = 1
    return
            

N,M,V = map(int, sys.stdin.readline().split())
tree = [[0]*(N+1) for _ in range(N+1)]
DFSv = [0 for _ in range(N+1)]
BFSv = [0 for _ in range(N+1)]

for _ in range(M):
    S, E = map(int, sys.stdin.readline().split())
    tree[S][E] = 1
    tree[E][S] = 1


DFS(V)
print()
BFS(V)

# 기초가 제일 중요하다.
# 혹시 DFS, BFS가 막힐 땐 이 문제를 다시 풀어보자