그냥 코딩하는 사람의 블로그

• https://docs.djangoproject.com/en/3.2/ref/databases/#mysql-notes

   

  Databases | Django documentation | Django

  Django The web framework for perfectionists with deadlines. Overview Download Documentation News Community Code Issues About ♥ Donate

  docs.djangoproject.com

연동 전 필요 라이브러리 설치

mysqlclient 설치

pip install mysqlclient

에러 발생할 경우 자가해결 방법(python3)

• https://pypi.org/project/mysqlclient/
• python3이 아닌 경우 python3부분만 python으로 바꾸어서 처리

sudo apt-get install python3-dev default-libmysqlclient-dev build-essential

Settings.py의 DataBase 수정

• 우선 기본적으로 설정되어있는 데이터베이스를 수정해 주어야 한다.
• 찾아보니 OPTIONS에 굳이 파일을 주지 않고 바로 NAME, USER, PASSWORD, HOST, PORT를 줘버려도 되지만, 파일이 훨씬 깔끔해 보여서 파일로 따로 지정

DATABASES = {
    'default': {
        'ENGINE': 'django.db.backends.mysql',
        'OPTIONS':  {
            'read_default_file': os.path.join(BASE_DIR, 'djangoproj.cnf'),
        }
    }
}

djangoproj.cnf

• db명, db ID, db PW, 기본 문자열셋 지정
• 호스트, 포트도 지정해주어야 함.. ⇒ 안해주면 에러가 나요..

[client]
database = djangoproject
user = root
password = root
default-character-set = utf8
host: 127.0.0.1
port: 3306

Database 생성

• 위에서 database = 에 적어준 이름을 가진 데이터베이스를 mysql에서 만들어 두어야 한다.

create database djangoproject character set utf8;

마이그레이션

python manage.py makemigrations
python manage.py migrate

• 마이그레이션까지 적용되었다면 mysql 연동이 끝남!

https://www.acmicpc.net/problem/3687

풀이 과정

1. 가장 큰 수를 만들려면 1, 7만으로 최대한 자리수를 늘리기만 하면 된다. (각각 2개, 3개이며 나머지는 4개 이상이므로 1 두개 넣는것보다 작음)

   • 성냥개비 개수가 홀수라면 맨앞에 7을 넣어주고 나머지는 1, 짝수라면 전체 1만으로 구성

2. BFS를 사용하여 DP 테이블을 채워준다.

   • 최대 100개의 성냥개비를 사용 가능하므로 100개까지 진행
   • DP[i]는 i개의 성냥개비로 만들 수 있는 수의 최솟값
   • 큐에 들어가는 형식은 [성냥개비 수, 만들어진 수]
   • 맨 앞자리는 0이 들어갈 수 없으므로, 초기 큐에는 1~9까지만 넣어준다.
   • 매 단계 큐에 넣을때마다 뒤에 09를 붙여주고, 09를 만드는데 필요한 성냥 수를 더해서 넘겨준다.
     • 성냥 수가 100개를 넘어가면 안됨.
   • 큐에서 빼낼 때, 만들어진 수가 기존 수보다 작을때만 뒤에 붙여주는 과정 진행

3. 최솟값, 최댓값 형식으로 출력시켜주면 된다.

• 최솟값이 굉장히 큰 수가 나올 수 있으므로 초기 값 설정을 잘 해주어야 함. 초깃값을 10e9로 했다가 처음엔 틀렸는데, sys.maxsize로 바꾸어주니 정답이 나옴.

import sys
from collections import deque

T = int(sys.stdin.readline().rstrip())

INT_MAX = int(sys.maxsize)

dp_max = [0] * 101
dp_min = [INT_MAX] * 101

count = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
initial = [[value, idx] for idx, value in enumerate(count)][1:]

queue = deque(initial)

while queue:
    cnt, make = queue.popleft()
    dp_min[cnt] = min(dp_min[cnt], make)
    if dp_min[cnt] != make:
        continue
    for i in range(10):
        if cnt + count[i] <= 100:
            queue.append([cnt + count[i], int(str(make)+str(i))])

for _ in range(T):
    p = int(sys.stdin.readline().rstrip())
    max_string = ''
    if p % 2 == 1:
        max_string = '7' + '1' * ((p-3) // 2)
    else:
        max_string = '1' * (p // 2)
    print(dp_min[p], max_string)

https://www.acmicpc.net/problem/15565

풀이 과정

1. 결국 1의 개수가 연속으로 딱 K개가 될 때중 하나가 가장 작은 연속된 인형들의 집합이다.
   • 따라서, 1의 위치들만 저장해둔 리스트들을 따로 만들어 둔다.
2. 1의 개수가 K개도 안된다면 애초에 불가능한 것이므로 -1 출력후 종료
3. 맨 앞에서부터 K개를 선택한다. => left는 0, right는 K-1이다.
   • 이 때, 인형의 개수는 리스트[right] - 리스트[left] + 1이므로, 이 값으로 최소 인형의 개수를 갱신해 준다.
   • 이후 한칸 옮겨서 left = left + 1, right = right + 1 해준다.
   • right가 배열의 끝까지 가게 되면 종료시켜 준다.
4. 최소 인형의 개수를 출력해 준다.

• 초기에는 막코딩 했는데 소스가 너무 지저분하고 이해하기 어려워서 맞았으나 다시 짬..

import sys

input = lambda :sys.stdin.readline().rstrip()

N, K = map(int, input().split())
dolls = list(map(int, input().split()))
answer = int(10e9)

lion_pos = []
for i in range(len(dolls)):
    if dolls[i] == 1:
        lion_pos.append(i)

left = 0
right = K-1

if len(lion_pos) < K:
    print(-1)
else:
    while right < len(lion_pos):
        answer = min(answer, lion_pos[right] - lion_pos[left] + 1)
        left, right = left+1, right+1
    print(answer)

이전 소스

• K개 맞추어 줄려고 매순간 값 갱신 이후에 left 1 증가시키고 lion 1 빼줌

import sys

input = lambda :sys.stdin.readline().rstrip()

N, K = map(int, input().split())

dolls = list(map(int, input().split()))


answer = int(10e9)

left = 0
right = 0
lion = 1 if dolls[0] == 1 else 0
while True:
    while right < len(dolls)-1 and lion < K:
        right += 1
        lion = lion + 1 if dolls[right] == 1 else lion

    while left < right and lion >= K:
        if dolls[left] == 1:
            if lion == K:
                break
            else:
                lion -= 1
        left += 1

    if lion >= K:
        answer = min(answer, right-left+1)

    left += 1
    lion -= 1

    if right == len(dolls)-1:
        break

if answer == int(10e9):
    print(-1)
else:
    print(answer)

https://www.acmicpc.net/problem/15961

풀이 과정

1. 일단 가장 왼쪽 초밥에서부터 연속해서 k개를 선택한다.

   • 이 때, 중복이 있을수 있으므로 초밥의 종류는 set에 저장하고 초밥의 개수는 딕셔너리에 저장한다.

2. 이제 왼쪽에서 한칸, 오른쪽으로 한칸 이동할 것이다.

   • 이전까지의 초밥의 종류가 0부터 k-1이라 하면 다음 초밥의 종류는 1부터 k, ...
   • left와 right를 1씩 증가하면서 배열의 크기를 넘어서는 경우가 있음
     • left = (left + 1) % 배열크기, right = (right+1) % 배열크기
   • 갱신하면서 왼쪽 딕셔너리의 값은 이동 전 1 감소시키고, 오른쪽 딕셔너리의 값은 이동 후 1 증가시킨다.
   • 딕셔너리의 값이 0이 되었다면 set에서 제거하고, 1이 되었다면 set에 추가한다.
   • 초밥의 최대 가짓수를 갱신해 주는데, 이 때 쿠폰 번호가 현재 초밥 종류에 속해 있다면 쓸수 없으므로 그대로, 속해있지 않다면 쓸수 있는 것이므로 1 더한 값으로 비교해 준다.

3. 왼쪽이 배열의 맨 마지막에 도달할때 까지 진행해 준다.

4. 초밥의 최대 가짓수를 출력해 준다.

소스 코드

import sys
from collections import defaultdict

input = lambda :sys.stdin.readline().rstrip()

N, d, k, c = map(int, input().split())
sushi = [int(input()) for _ in range(N)]
case = set()
case_count = defaultdict(int)
answer = 0

left = 0
right = k-1

for i in range(k):
    case.add(sushi[i])
    case_count[sushi[i]] += 1

total_case = len(case)+1 if c not in case else len(case)
answer = max(answer, total_case)


for i in range(N):
    case_count[sushi[left]] -= 1
    if case_count[sushi[left]] == 0: case.remove(sushi[left])
    left = (left + 1) % N

    right = (right + 1) % N
    if sushi[right] not in case: case.add(sushi[right])
    case_count[sushi[right]] += 1

    total_case = len(case)+1 if c not in case else len(case)
    answer = max(answer, total_case)

print(answer)

풀이 과정

• 퇴실 순서는 리스트에서 큐 형태로 바꾸어 줌.
  => 구현의 편의성을 위해 큐로 바꾸어주는게 좋음!

• 구현의 편의를 위해 처음 인원수 저장할 때는 인원수 + 1만큼의 배열을 만들어 두고, 리턴할 때는 첫번째 인덱스부터 리턴

• 입실한 사람 순서대로 반복문을 진행한다.

  • 입실한 사람은 set에다가 넣어준다. (비교의 용이, 속도 면에서 좋을 것 같아서)
  • 입실 처리가 되었으면 퇴실 인원이 있는지도 확인한다.
  • 퇴실 인원의 확인은 큐의 맨 앞을 확인하면 되며, 퇴실 인원이라면 큐에서 빼준다.
    • 빼주면서 인원 처리를 해주어야 하는데, 빼낸 사람을 제외한 기존 입실 처리된 인원들은 빼낸 사람을 만났으므로, 기존 입실 처리된 인원들이 만난 사람 수에는 1을 더해준다
  • 또한, 빼낸 사람의 인원에는 빼낸 사람을 제외한 기존 입실 처리된 인원들의 수를 더해준다.

소스 코드

def solution(enter, leave):
    answer = [0] * (len(enter) + 1)
    leave = deque(leave)
    visited = set()

    for e_person in enter:
        visited.add(e_person)
        while leave:
            if leave[0] in visited:
                answer[leave[0]] += (len(visited) - 1)
                visited.remove(leave.popleft())
                for left_person in visited:
                    answer[left_person] += 1
            else:
                break

    return answer[1:]

출처

• https://programmers.co.kr/learn/courses/30/lessons/86048

문제 설명

문제

게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.

예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 이를 IF문으로 작성한다면 아래와 같이 구현할 수 있다.

    if power <= 10000 
        print WEAK 
    else if power <= 100000 
        print NORMAL 
    else if power <= 1000000 
        print STRONG

혼자서 게임을 개발하느라 매우 바쁜 밀리를 대신해서, 캐릭터의 전투력에 맞는 칭호를 출력하는 프로그램을 작성하자.

입력

첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M≤ 105)

두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 109 이하의 음이 아닌 정수가 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다.

N + 2번째 줄부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.

출력

M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

풀이 과정

1. 입력받은 칭호와 전투력을 딕셔너리 형태로 저장, 전투력만 따로 리스트에 저장

   • dict[전투력] = 칭호 형식

2. 칭호 전투력 리스트를 정렬

   • 이분탐색을 하기 위함

3. 칭호 전투력 리스트에 대해 이분탐색 진행

   • 리스트의 중간값이 입력받은 값보다 크면 왼쪽 구간 진행
   • 리스트의 중간값이 입력받은 값보다 작으면 오른쪽 구간 진행
   • 단, 여기서 왼쪽 구간 진행할 때는 최댓값을 구해야 하므로 현재 중간값을 저장해 두어야 한다.

4. 입력받은 중간값에 대응하는 칭호 출력

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()

N, M = map(int, input().split())

types = {}

def bisect(value, arr):
    left = 0
    right = len(arr)-1
    target = 0
    while left <= right:
        mid = (left + right) // 2

        if arr[mid] >= value:
            target = mid
            right = mid - 1
        else:
            left = mid + 1

    return target

values = []
for _ in range(N):
    name, value = input().split()
    value = int(value)
    if types.get(value) == None:
        types[value] = name
        values.append(int(value))

values.sort()
for _ in range(M):
    value = int(input())
    pos = bisect(value, values)
    print(types[values[pos]])

문제 설명

문제

N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면,

색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다.

입력

첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 같고, 9.9보다 작거나 같다.

출력

계산된 최댓값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다.

풀이 과정

1. 현재 위치를 i라고 할 때, i에 올수 있는 경우는 두가지이다.

   • 이전까지의 곱에 i를 곱하는 경우
   • i에서 시작하는 경우

2. 따라서, 두가지 경우중 최댓값을 dp[i]로 설정해주면 된다.

3. 마지막으로, 출력 형식을 잘 보아야 함.

   • 4번째 자리에서 반올림 시킨후 소수점 셋째자리까지 출력해주어야 함.
   • 1 (x) 1.000 (o)

소스 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())
numbers = [float(input().rstrip()) for _ in range(N)]
dp = [0] * N

dp[0] = numbers[0]

for i in range(N):
    if i > 0:
        dp[i] = max(dp[i-1] * numbers[i], numbers[i])

print("%.3f"%(round(max(dp), 3)))

풀이 과정

1. 파이썬으로는 풀이할 수가 없어서 Java로 풀이함.
2. 전체적인 흐름은 BFS로 구성
   • 전체 배열을 2중 for문으로 검사하면서, 0이 아닌 수가 발견되면 그 자리에서 bfs 진행
   • bfs의 경우, 현재 자리의 값을 0으로 만들고 현재 자리의 값과 같은 값이 인접 위치에 있다면, 해당 위치를 0으로 만들고 큐에 넣는 방식으로 진행.
   • 0으로 만든 배열 요소의 수를 따로 리턴해 준다.
3. 전체 BFS 진행 횟수가 영역의 개수, BFS 진행하면서 0으로 만든 배열 요소의 수의 최댓값이 가장 큰 영역의 넓이이다.

• 문제 오류인것 같긴 한데.. 입력받은 picture을 직접 수정하면 틀렸다고 나오고, picture를 따로 복사한 다음 수정해야 맞았다고 나온다..

소스 코드

import java.util.Queue;
import java.util.LinkedList;

class Position {
    int x;
    int y;

    public Position(int a, int b) {
        this.x = a;
        this.y = b;
    }
}

class Solution {
    public int bfs(int curX, int curY, int[][] picture) {
        Queue<Position> queue = new LinkedList<Position>();
        int areaValue = picture[curX][curY];
        queue.add(new Position(curX, curY));
        picture[curX][curY] = 0;
        int count = 1;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!queue.isEmpty()) {
            Position pos = queue.poll();
            for (int i = 0; i<4; i++) {
                int nx = pos.x + dx[i];
                int ny = pos.y + dy[i];
                if (0 <= nx && nx < picture.length && 
                    0 <= ny && ny < picture[0].length && 
                    picture[nx][ny] == areaValue) {
                    queue.add(new Position(nx, ny));
                    count++;
                    picture[nx][ny] = 0;
                }
            }
        }

        return count;
    }

    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        int[][] copypicture = new int[picture.length][picture[0].length];

        for (int i = 0; i<m; i++)
            for (int j=0; j<n; j++)
                copypicture[i][j] = picture[i][j];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (copypicture[i][j] != 0) {
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, bfs(i, j, copypicture));
                    numberOfArea++;
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
}

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

• 1, 2주차에 비해 난이도가 극악무도해져서 최대한 나중에 풀음ㅜㅜ
• 전체적으로 세개의 과정으로 나눌 수 있다.
  1. board에서 빈 블록 구하기
  2. table에서 넣을 블록 구하기
  3. (1)번에서 구한 빈 블록에 (2)번에서 구한 블록들을 1번, 2번, 3번, 4번 회전시키면서 넣어보고 맞는지 확인

1. board에서의 빈 블록과, table에서 넣을 블록들을 bfs로 구한다.
   • 이 때, 편의를 위해 블록들을 최대한 왼쪽 위로 붙여준다.
   • 예시로 4,4->4,5->4,6 블록을 (0,0 -> 0,1 -> 0,2)로 바꾸어 준다.
   • 방식은 블록들의 행의 최솟값과 열의 최솟값을 전체 블록에 빼주면 된다.
2. 블록 회전을 구현한다.
   • 블록 회전은 각 블록이 [행, 열]에 있을 때,
   • 회전된 블록은 [(블록들의 최대 열 - 현재 열), 행] 위치를 갖게 된다.
3. 이제 빈 블록에 대해서 블록들이 들어가는지 확인한다.
   • 블록을 4번 회전시키면 다시 자기자신으로 돌아오므로, 4번 회전시키면서 각각의 경우의 수에 대해 들어가는지 확인
   • 확인할 때 방식은 블록들과 빈 블록의 교집합을 하여, 교집합의 원소의 개수가 블록의 개수와 일치하면 블록이 들어가는것이다.

• 풀고나서 돌아보니 엄청 어려웠던것 같진 않은데.. 풀때는 되게 고민을 많이 한 문제였던 것 같다.

소스 코드

from collections import deque

def get_movement(arr, position, org_value, change_value):
    # board의 경우 org_value, change_value가 0, 1
    # table의 경우 org_value, change_value가 1, 0

    x, y = position[0], position[1]
    movement = [[x, y]]
    queue = deque([[x, y]])
    arr[x][y] = change_value
    min_x, min_y = x, y
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    length = len(arr)

    while queue:
        nx, ny = queue.popleft()
        for i in range(4):
            mx, my = nx + dx[i], ny + dy[i]
            if 0 <= mx < length and 0 <= my < length and arr[mx][my] == org_value:
                arr[mx][my] = change_value
                min_x, min_y = min(mx, min_x), min(my, min_y)
                movement.append([mx, my])
                queue.append([mx, my])

    movement = list(map(lambda f:(f[0]-min_x, f[1]-min_y), movement))
    return movement

def get_total_list(arr, f, value):
    length = len(arr)
    total_list = []
    org_value = value
    change_value = 1 if value == 0 else 0
    for i in range(length):
        for j in range(length):
            if arr[i][j] == value:
                total_list.append(f(arr, [i, j], org_value, change_value))

    return total_list

def rotate(block):
    max_col = max(map(lambda x:(x[1]), block))
    return list(map(lambda x:(max_col-x[1], x[0]), block))


def solution(game_board, table):
    answer = 0
    total_blank = get_total_list(game_board, get_movement, 0)
    total_block = get_total_list(table, get_movement, 1)
    used = [False] * len(total_block)
    for idx1, blank in enumerate(total_blank):
        for idx2, block in enumerate(total_block):
            if used[idx2] or len(blank) != len(block):
                continue

            temp = block
            find = False
            for i in range(4):
                temp = rotate(temp)
                if len(set(temp) & set(blank)) == len(temp):
                    find = True
                    break

            if find:
                used[idx2] = True
                answer += len(block)
                break

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제 설명

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이 과정

1. DP를 진행한다.
   • 수열에서 수를 하나 제거할 수 있으므로
   • DP[i][0]: 수를 제거하지 않은 경우
   • DP[i][1]은 수를 제거한 경우
2. 현재 선택한 수열의 인덱스를 i라고 두고, 입력받은 정수 배열명을 temp라고 할 때
   • 수를 제거하지 않은 경우에는 두가지 케이스가 올 수 있다.
     1. 이전 합계를 끌고와서 자기 숫자를 더해주는 경우
        => dp[i][0] = dp[i-1][0] + temp[i]
     2. 이전 합계가 음수여서 자기 자신에서 시작하는 경우
        => dp[i][0] = temp[i]
     3. 둘중 최댓값을 dp[i][0]에 대입해준다.
   • 수를 제거한 경우에는 두가지 케이스가 올 수 있다.
     4. 자기 숫자를 제거하는 경우
        => dp[i][1] = dp[i-1]
     5. 이전에 이미 숫자가 제거된 경우
        => dp[i][1] = dp[i-1] + temp[i]
     6. 둘중 최댓값을 dp[i][0]에 대입해준다.
3. 전체 테이블에 대한 최대값을 구하면 된다.
   • 단, n이 1일 때는 무조건 선택해야 하므로 입력받은 수를 바로 리턴해주면 된다.

소스 코드

N = int(input())
temp = list(map(int, input().split()))

dp = [[0, 0] for _ in range(N)]
dp[0][0], dp[0][1] = temp[0], 0


m = -int(10e9)
for i in range(1, N):
    dp[i][0] = max(temp[i], dp[i-1][0] + temp[i])
    dp[i][1] = max(dp[i-1][0], dp[i-1][1] + temp[i])

if N == 1:
    print(temp[0])
else:
    for i in range(1, N):
        m = max(m, dp[i][0], dp[i][1])
    m = max(m, dp[0][0])
    print(m)