CodeDrive

문제:

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력:

영상을 압축한 결과를 출력한다.

풀이방법:

 분할정복을 사용해서 풀어야 하는 문제다. 반복해서 영상을 4분할로 나누면서, 같은 숫자로 구성되어 있는지 파악하면 된다.

 각 분할된 분면에서 왼쪽 상단에 있는 점을 기준점으로 삼아서, 반복문을 순회하면서 같은 숫자로 구성되어 있는지 확인한다.

 만약 같은 숫자로 구성되어 있으면 더 이상 분할할 필요가 없으니 현재 기준점을 출력하도록 한다. 하지만 같은 숫자로 구성되어 있지 않다면 재귀적으로 지금 영상을 4분할로 나눠서 위의 작업을 반복해주면 된다.

문제링크:

www.acmicpc.net/problem/1992

문제:

주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.

A, B, C, D, E, F에 쓰여 있는 수가 주어진다.

지민이는 현재 동일한 주사위를 N^3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N*N*N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.

N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수는 50보다 작거나 같은 자연수이다.

출력:

첫째 줄에 문제의 정답을 출력한다.

풀이방법:

 주사위를 쌓아서 N*N*N 크기의 정육면체를 만들게 되면, 밖으로 노출되는 면이 가장 많은 경우는 3개인 면인 경우이다. 정육면체에서 3개의 면 주사위의 개수, 2개의 면 주사위의 개수, 1개의 면 주사위의 개수는 N에 따라서 달라지게 된다.

1. 3개의 면 주사위의 개수는 항상 위쪽 면의 꼭짓점에서만 나타나므로 N과 상관없이 4번만 등장하게 된다.

2. 2개의 면이 나타나는 주사위의 개수는 모서리에서만 나타나게 된다. 이 때 위쪽 면에서는 꼭짓점에서 이미 사용한 주사위가 있으므로 이를 제외해주고 계산해줘야 한다. 따라서 (N-1)*4+(N-2)*4개가 존재한다.

3. 1개의 면이 나타나는 주사위는 ((N-2)^2)*5+(N-2)*4 개 있다.

 주사위는 위 그림에서 나타나는 것처럼 전개도를 따라서 접게 되므로, 모든 숫자 중에서 가장 작은 3개(혹은 2개)를 골라서 최솟값을 구하면 안된다. A에 있는 숫자는 F와 만날 수 없기 때문이다. 따라서 나타날 수 있는 3개인 경우는 [(0,1,2),(0,1,3),(0,2,4),(0,3,4),(1,2,5),(1,3,5),(2,4,5),(3,4,5)]와 같기 때문에 이 중에서 가장 작은 값을 가지는 경우를 찾도록 하고, 2개인 경우는 서로 반대 면에 있는 숫자만 피하면 되므로, 이를 제외하고 계산하도록 한다.

 N이 1인 경우는 위에서 구한 케이스 구분이 필요없기 때문에 따로 처리하도록 한다.

문제링크:

www.acmicpc.net/problem/1041

문제:

Lucky Set이란 정수의 집합이다.

구간 [A,B]란 A보다 크거나 같고, B보다 작거나 같은 모든 정수가 있는 구간이다. 이때, A와 B는 모두 양수이고, B는 A보다 크다.

구간 [A,B]가 Unlucky가 되기 위해선 구간에 속한 모든 정수가 Lucky Set에 없어야 한다.

Lucky Set과 N이 주어질 때, N을 포함하는 Unlucky 구간의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다. 마지막 줄에는 N이 주어진다. N은 lucky Set에서 가장 큰 수보다 작거나 같은 자연수이다.

출력:

첫재 줄에 문제의 정답을 출력한다.

풀이방법:

N이 Lucky set의 어느 구간에 속해 있는지 파악해야 한다. 이 때, N이 lucky set의 원소일 수 있으므로 주의해서 탐색해야 한다. 반복문을 사용해서 N이 속해 있는 구간을 파악하고 왼쪽 값을 left, 오른쪽 값을 right라고 설정한다. N이 lucky set의 원소보다 다 작은 경우는 예외케이스로 판단하도록 한다.

left 와 right를 구한 뒤에는 이중반복문을 사용해서 구간을 생성하여, 이 구간 내에 N이 있는 경우에만 answer에 값을 더하도록 한다.

문제링크:

www.acmicpc.net/problem/1059

문제:

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력:

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력:

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

풀이방법:

유니온-파인드 알고리즘을 사용해서 문제를 풀려고 한다. 우선 초기 게이트들은 각자 번호로 초기화를 한다. 그리고 앞으로 들어오는 비행기를 게이트에 할당하기 시작한다. 이 때 할당하는 방법은 find()함수로 진행을 하며, 비행기의 번호에 따라 가장 큰 게이트에 도킹을 한다. 즉 gi번 비행기는 gi게이트에 할당하도록 하고, 만약 gi게이트에 이미 도킹 된 비행기가 있다면 그 전 게이트(gi-1)에 할당한다. 이렇게 계속해서 할당을 하다가 0번째 게이트를 만나게 되면 더 이상 도킹을 진행할 수 없기 때문에 공항을 폐쇄한다.

문제링크:

www.acmicpc.net/problem/10775

문제:

워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자.

두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다.

편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n>= m 이라고 가정해도 무리가 없다. n < m이면 어차피 P는 중간에 나타날 수 없기 때문이다. 또, T의 i번째 문자를 T[i]라고 표현하도록 하자. 그러면 물론, P의 i번째 문자는 P[i]라고 표현된다.

문자열 P가 문자열 T 중간에 나타난다는 것, 즉 문자열 P가 문자열 T와 매칭을 이룬다는 것이 어떤 것인지 아래의 두 예를 통해 알아보자. 위의 예에서 P는, T의 1번 문자에서 시작하는 매칭에 실패했다. T의 7번 문자 T[7]과, P의 7번 문자 P[7]이 서로 다르기 때문이다.

 그러나 아래의 예에서 P는, T의 5번 문자에서 시작하는 매칭에 성공했다. T의 5~11번 문자와 P의 1~7번 문자가 서로 하나씩 대응되기 때문이다.

가장 단순한 방법으로, 존재하는 모든 매칭을 확인한다면, 시간 복잡도가 어떻게 될까? T의 1번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 1~m번 문자와 P의 1~m번 문자를 비교한다면 최대 m번의 연산이 필요하다. 이 비교들이 끝난 후, T의 2번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 2~m+1번 문자와 P의 1~m번 문자를 비교한다면 다시 최대 m번의 연산이 수행된다. 매칭은 T의 n-m+1번 문자에서까지 시작할 수 있으므로, 이러한 방식으로 진행한다면 O((n-m+1)*m = O(nm)의 시간복잡도를 갖는 알고리즘이 된다.

 더 좋은 방법은 없을까? 물론 있다. 위의 제시된 예에서, T[7] ≠ P[7] 이므로 T의 1번 문자에서 시작하는 매칭이 실패임을 알게 된 순간으로 돌아가자. 이때 우리는 매칭이 실패라는 사실에서, T[7] ≠ P[7] 라는 정보만을 얻은 것이 아니다. 오히려 i=1,...,6에 대해 T[i] = P[i]라고 하는 귀중한 정보를 얻지 않았는가? 이 정보를 십분 활용하면, O(n)의 시간 복잡도 내에 문자열 매칭 문제를 풀어내는 알고리즘을 설계할 수 있다.

P 내부에 존재하는 문자열의 반복에 주목하자. P에서 1, 2번 문자 A, B는 5,6번 문자로 반복되어 나타난다. 또, T의 1번 문자에서 시작하는 매칭이 7번 문자에서야 실패했으므로 T의 5,6번 문자도 A,B이다.

따라서 T의 1번 문자에서 시작하는 매칭이 실패한 이후, 그 다음으로 가능한 매칭은 T의 5번 문자에서 시작하는 매칭임을 알 수 있다! 더불어, T의 5~6번 문자는 P의 1~2번 문자와 비교하지 않아도, 서로 같다는 것을 이미 알고 있다! 그러므로 이제는 T의 7번 문자와 P의 3번 문자부터 비교해 나가면 된다.

 이제 이 방법을 일반화 해 보자. T의 i번 문자에서 시작하는 매칭을 검사하던 중 T[i+j-1] ≠ P[j]임을 발견했다고 하자. 이렇게 P의 j번 문자에서 매칭이 실패한 경우, P[1…k] = P[j-k…j-1]을 만족하는 최대의 k(≠j-1)에 대해 T의 i+j-1번 문자와 P의 k+1번 문자부터 비교를 계속해 나가면 된다.

 이 최대의 k를 j에 대한 함수라고 생각하고, 1～m까지의 각 j값에 대해 최대의 k를 미리 계산해 놓으면 편리할 것이다. 이를 전처리 과정이라고 부르며, O(m)에 완료할 수 있다.

 이러한 원리를 이용하여, T와 P가 주어졌을 때, 문자열 매칭 문제를 해결하는 프로그램을 작성하시오.

입력:

첫째 줄에 문자열 T가, 둘째 줄에 문자열 P가 주어진다. 문자열 내에 공백이 포함되어 있을 수도 있음에 유의한다. 물론 공백도 하나의 문자로 인정된다. T와 P의 길이 n, m은 1이상 100만 이하이다.

출력:

첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다.

풀이방법:

이 문제에 대한 설명은 KMP 알고리즘에 대한 설명이다. KMP 알고리즘은 bowbowbow.tistory.com/6이 곳에서 정말 잘 설명하고 있는 것 같다. 다음은 해당 링크의 설명을 바탕으로 작성한 코드입니다.

문제링크:

www.acmicpc.net/problem/1786

문제:

감수성이 뛰어난 음유시인 영재는 일상생활 중에 번뜩 시상이 떠오르곤 한다.

하지만 기억력이 좋지 못한 영재는 시상이 떠오르면 그 순간 컴퓨터로 기록해야만 안 까먹는다! 시는 대문자, 소문자 알파벳과 빈칸으로 이루어져 있따. 시상은 매번 훌륭하지만 제목 짓는 센스가 부족한 영재는 시에 나오는 단어들의 첫 글자를 대문자로 바꾼 뒤 순서대로 이어서 제목을 만든다. 만약 시의 내용이 'There is no cow level' 이라면 시의 제목은 'TINCL'이 된다.

시도 때도 없이 시를 기록하느라 낡아버린 영재의 키보드는 수명이 얼마 남지 않았다. 앞으로 스페이스 바와 영자판을 누를 수 있는 횟수가 정해져 있어 이를 초과하면 키보드가 수명이 다 하여 어떠한 작업도 하지 못하게 된다. 하나 다행인 점은, 키보드를 쓸 때 같은 문자가 연속으로 나오거나 빈칸이 연속으로 나오는 경우 영재는 자판을 꾹 눌러 한 번만 사용해서 키보드를 좀 더 효율적으로 쓸 수 있다. (A와 a는 다른 문자이므로 'Aa'는 2번의 a자판을 누른 것으로 한다.

시의 내용과 시의 제목은 Enter 키로 구분된다. 다향히 Shift 키와 Enter 키는 항상 수명이 무한한 상황이다!

음유시인 영재가 이번에 지은 시의 내용과 스페이스 바와 영자판을 누를 수 있는 횟수가 주어졌을 때, 시의 내용과 제목을 모두 기록할 수 있다면 시의 제목을 출력하고, 만약 키보드의 수명이 다 하여 기록을 완벽하게 못 하게 된다면 -1을 출력하여라.

입력:

첫 줄에 시의 내용이 주어진다.

둘째 줄에는 스페이스 바의 남은 사용 가능 횟수가 주어진다.

셋째 줄에는 대소문자를 구별하지 않고, 26개의 알파벳에 대한 영자판의 남은 사용 가능 횟수가 알파벳순으로 주어진다.

출력:

시의 내용과 제목을 모두 기록할 수 있다면 제목을 출력하여라.

만약 키보드의 수명이 다 하여 기록을 완벽하게 못 하게 되어 작업을 하지 못한다면 -1을 출력하여라.

풀이방법:

주어진 조건대로 구현을 해서 풀면 된다. 이 문제에서 고려해야 하는 조건들은 다음과 같다.

1. 시의 내용과 제목을 모두 작성할 수 있어야 한다.

2. 연속된 문자는 효율적으로 작성을 할 수 있지만 대,소문자 구분은 해야 한다.

1을 위해서 두 번 체크 하는 과정이 필요하다. 2를 위해서는 문자열을 비교하는 것은 대소문자로 비교를 하고, 남은 횟수를 줄일 때는 소문자로 바꿔서 진행하도록 한다.

문제링크:

www.acmicpc.net/problem/19948

문제:

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

- 3 : 3 (한 가지)

- 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)

- 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 N이 주어진다. (1<=N<=4,000,000)

출력:

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

풀이방법:

투 포인터를 사용하는 슬라이딩 윈도우랑 소수를 구하는 알고리즘 중 하나인 에라토스테네스의 체를 사용하도록 한다.

우선 자연수 N 이하의 소수들을 에라토스테네스의 체를 이용해서 찾는다. 이 때, 소수인 값들만 남기기 위해서 set을 사용해서 소수가 아닌 것들을 제거하도록 했다.

이렇게 자연수 N 이하의 소수들이 담긴 배열을 구했으면, 이를 투 포인터를 이용한 슬라이딩 윈도우를 통해서 부분합을 구한다. 자연수 N보다 부분합이 작다면 end를 움직여서 부분합을 증가시키고, 부분합이 더 크다면 start를 줄여서 부분합을 증가시킨다.

N이 되는 경우는 count를 1씩 늘리며 부분합을 줄이도록 한다.

문제링크:

www.acmicpc.net/problem/1644

문제:

2048 게임은 4x4 크기의 보드에서 혼자 즐기는 게임이다. 

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 디시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

이 문제에서 다루는 2048 게임은 보드의 크기가 NxN이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 쵣 5번 이동해서 만들 수 있는 가장 큰 불록의 값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 보드의 크기 N (1<=N<=20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력:

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

풀이방법:

최대 5번만 이동하면 되기 때문에 dfs를 사용해서 모든 경우를 탐색하고, 그 중 가장 최댓값을 찾아내도록 하면 된다.

반복문을 사용해서 상하좌우로 이동하게 만들었다.

문제링크:

www.acmicpc.net/problem/12100

문제:

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N (10<=N<=100,000)과 S (0<S<=100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력:

첫째 줄에 구호고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

풀이방법:

시작과 끝을 나타내는 두 포인터를 통해서 연속된 부분합을 구하도록 한다. 두 포인터들은 다음 두 규칙에 따라 움직인다.

1. 두 포인터 사이의 합이 S를 넘지 않는다면 end 포인터를 이동시켜서 연속된 수의 길이를 늘린다.

2. 두 포인터 사이의 합이 S를 넘었다면(이상이라면), 현재 길이가 최소인지 확인한다. 그리고 start 포인터를 늘려서 연속된 수의 길이를 줄인다.

3. 1,2의 행동을 end가 수열의 길이를 초과하거나, start가 end 포인터를 넘어갈 떄까지 반복한다.

위 규칙을 마치고 난 다음에 초기 answer 값이 변하지 않았다면 조건을 만족하는 부분합을 찾지 못한 것이기 때문에 0을 출력하고, 아니면 정답을 출력하면 된다.

<2022-02-05> 재채점으로 인한 수정

부분합이지만 하나의 값으로만 S를 넘은 case가 존재한다.

10 10

10 1 1 1 1 1 1 1 1 1

ans 1

문제링크:

www.acmicpc.net/problem/1806

문제:

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 불어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표가 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력:

첫째 줄에 N(1<=N<=100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0,1,2,3,4,5,6,7,8,9 중의 하나가 된다.

출력:

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

풀이방법:

 가로의 길이가 세 개로 고정되어 있기 때문에 그림의 세 조건에서 파란 동그라미에 해당하는 부분들에서 값을 가져와서 최댓값과 최솟값을 계산하면 된다.

 하지만 이 문제에는 메모리 제한이 걸려 있었는데, N이 최대 100,000까지 존재하기 때문에 초기에 이 배열을 모두 초기화하고 더해나가면 메모리 초과가 발생하게 된다. 따라서 처음부터 N만큼의 배열을 초기화하지 않고, 한 줄씩 입력 받으며 최댓값과 최솟값을 바꾸어 나가도록 한다.

0번째 인덱스에서는 이전 행의 0번째와 1번째 값에만 영향을 받으며,

1번째 인덱스는 이전 행 전체에서,

2번째 인덱스는 이전 행의 1번째와 2번째 값에만 영향을 받는다.

max와 min을 사용해 각 칸을 tuple 형식으로 업데이트 했다. (max값, min값) 그리고 마지막에서는 max와 min의 key 옵션을 활용해서 전체 최대 점수와 최소 점수를 구하도록 했다.

문제링크:

www.acmicpc.net/problem/2096