ebson

1. dp 배열을 N+1 * N+1 의 크기로 초기화한다. 2. dp[1][x] 값을 cards[1] * x 값으로 초기화한다. 3. dp[ci][ni] 값을 카드를 ci번째까지 검사했을 때 총 ni 개의 카드를 갖는 최대 가격으로 저장한다. 3.1. 이전 검사에서 ni개의 카드를 갖는 최대 가격 -> dp[ci-1][ni] 3.2 이전 검사에서 ni-ci개의 카드를 갖는 최대가격 + ci개에 해당하는 카드 가격 -> dp[ci-1][ni-ci] + cards[ci] 3.3. 현재 검사에서 ni-ci개의 카드를 갖는 최대가격 + ci개에 해당하는 카드 가격 -> dp[ci][ni-ci]+cards[ci] 를 비교하고 3.4. 현재 검사에서 ni-(1이상ni미만)개의 카드를 제외하는 경우의 최대 가격 + ..

1. 문자열 A, B를 저장 2. 문자열 B의 길이만큼 dp 배열을 0으로 초기화 3. A 문자열을 순회하면서 아래를 반복 3.1. cnt 변수를 0 으로 초기화 3.2. B 문자열을 순회하면서 아래를 반복 3.2.1. cnt가 dp[bi] 보다 작으면, cnt에 dp[bi]값을 저장 3.2.2. A[ai] 값과 B[bi] 값이 같으면, dp[bi] 값에 cnt+1 값을 저장 4. dp에서 최대값을 출력 A = input() B = input() dp = [0 for _ in range(len(B))] for ai in range(len(A)): cnt = 0 for bi in range(len(B)): if cnt < dp[bi]: cnt = dp[bi] elif A[ai] == B[bi]: dp[bi..

1. dp 리스트를 wines 리스트 길이 만큼 0으로 초기화한다. 2. wines의 길이 N이 1 이면 첫번째 포도주의 양을 출력한다. 3. N이 2이면 첫번째와 두번째 포도주의 양의 합을 출력한다. 4. N이 2보다 크면 dp[0]에 첫번째 포도주의 양, dp[1]에 첫번째와 두번째 포도주의 양의 합을 저장한다. 5. dp의 3번째 요소부터 마지막 요소까지 아래를 반복해 값을 갱신한다. 5.1. dp[i]에는 i번째 포도주를 마시지 않는 경우, i번째 포도주를 마시고 그 이전에도 마신 경우, i번째 포도주를 마시고 그 이전에는 마시지 않은 경우 중 최대값을 저장한다. 6. dp 리스트의 마지막 값을 출력한다. N = int(input()) wines = [int(input()) for _ in ran..

1. 삼각형의 크기 N이 1이면 첫번째 줄의 첫번째 수를 출력한다. 2. 그렇지 않다면, dp 리스트를 N개의 리스트로 초기화한다. 3. dp 리스트의 0번째 리스트로 삼각형의 첫번째 줄을 저장한다. 4. dp 리스트의 1번째 리스트로 삼각형의 두번째 줄의 각 수에 첫번째 줄의 수를 더한 리스트를 저장한다. 5. N 이 2라면, dp 리스트의 1번째 리스트의 두 수 중 큰 수를 출력한다. 6. N 이 2보다 크면, 아래를 dp 리스트의 마지막 요소까지 반복한다. 6.1. dp 리스트의 i번째 요소로 정수 리스트를 입력받아 저장한다. 6.2. dp 리스트의 i번째 리스트를 순회하면서 아래 6.2.1. ~ 6.2.3. 을 반복한다. 6.2.1. 0번째 요소이면, 0번째 요소에 이전 리스트의 0번째 요소를 더..

1. R, G, B 를 선택한 경우 N번 집까지 가는 최소값을 각각 dp[n][0], dp[n][1], dp[n][2] 으로 저장한다.2. dp[n-1][0], dp[n-1][1], dp[n-1][2] 중 최소값을 출력한다. N = int(input())dp = [list(map(int, input().split())) for _ in range(N)]for i in range(1, len(dp)): dp[i][0] += min(dp[i-1][1], dp[i-1][2]) dp[i][1] += min(dp[i-1][0], dp[i-1][2]) dp[i][2] += min(dp[i-1][0], dp[i-1][1])print(min(dp[N-1][0], dp[N-1][1], dp[N-1][2]..

1. 첫번째 배열에서 가능한 모든 부분배열의 합을 N_sums 리스트에 저장한다. 2. 두번째 배열에서 가능한 모든 부분배열의 합을 M_sums 리스트에 저장한다. 3. 첫번째 배열의 모든 요소를 순회하면서 아래 3.1.-3.3 을 반복한다. 3.1. M_sums에서 bisect_right으로 T-첫번째 배열의 요소 값을 탐색한 인덱스를 r에 저장한다. 3.2. M_sums에서 bisect_left으로 T-첫번째 배열의 요소 값을 탐색한 인덱스를 l에 저장한다. 3.3. r-l을 cnt변수에 증감한다. 4. 모든 가능한 경우의 수 cnt를 출력한다. T = int(input()) N = int(input()) N_list = list(map(int, input().split())) M = int(inpu..

1. 주어진 중량값 중 최소, 최대값을 저장 2. 1번의 최소, 최대 중량값을 lo, hi에 저장하고 중간값을 mid에 저장한다. mid를 최소무게제한으로 하여 아래 이분탐색 3-5를 반복한다. 3. 최소무게제한을 통과하는 노드만 방문하도록 하여 시작점에서 끝점까지 이동가능한지 여부를 반환하는 bfs를 아래와 같이 실행한다. 3.1. 최소무게제한을 인자로 받고 deque에 시작점을 저장한다. 3.2. 방문체크배열을 노드개수 + 1개 만큼 False으로 초기화하고 시작점을 True로 갱신한다. 3.3. deque에 요소가 없을 때까지 아래를 반복한다. 3.3.1. deque에서 맨 왼쪽 요소를 꺼낸다. 3.3.2. 맨 왼쪽요소에서 갈 수 있는 노드와 그 중량값에 대해 만약 방문하지 않은 노드이고 중량값이 ..

1. lo를 0, hi를 기타 레슨 시간 목록 lectures의 총합으로 초기화한다. 2. 출력할 변수 ans에는 hi를 저장한다. 3. lo가 hi이하이면 아래 4-9를 반복한다. 4. mid에 (lo+hi)//2를 저장한다. 5. mid가 lectures 요소 중 최대값보다 작으면, lo를 mid+1으로 저장하고 다음 반복으로 넘어간다. 6. sub를 0, sub_cnt를 1으로 초기화하고 lectures를 순회하면서 아래 6.1-6.2를 반복한다. 6.1. sub에 lectures의 요소를 더한 값이 mid 이하이면 sub에 lectures의 요소를 더한다. 6.2. 만약 mid보다 크다면 sub_cnt에 1을 더하고 sub에는 lectures의 요소를 저장한다. 7. sub_cnt가 M(블루레이의..