Kakao Blind 2022 - 파괴되지 않은 건물 Level Ⅲ Kakao Blind 2022 - 파괴되지 않은 건물 문제 2차원 배열에서 특정 구간에 덧셈, 뺄셈을 진행하고 이를 효율적으로 시간 단축하는 문제입니다. 입력 출력 단순히 더하고 빼는 연산을 에 해결하더라도 정확도는 쉽게 100% 맞출 수 있습니다. 하지만, 이 문제는 효율성 문제로 시간 복잡도를 줄여야 합니다. 🍺 How to Solve? 🔥 Key Point 어떻게 하면 구간에 대해서 더하고, 빼는 연산을 매번 하지 않고 한 번에 할 수 있을까?? 🎯 2차원 배열에서 누적합을 이용한다. 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 위 상황에서 (3,3) 부터 (5,5) 까지 -4 만큼 적용한다면? 모든 구간에 적용할 필요 없이 각 사각형의 오른쪽 아래 끝 좌표에만 기록을 한다면 (0,0) 부터 해당 구간까지에는 x만큼 적용하겠다는 의…

BOJ 2632 - 피자 판매 Gold Ⅱ BOJ 2632 - 피자 판매 문제 고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다. 그림1 고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다. 그림2 피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로…

BOJ 2263 - 트리의 순회 Gold Ⅱ BOJ 2263 - 트리의 순회 문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력 첫째 줄에 프리오더를 출력한다. ✨ PreOrder, PostOrder, InOrder란? 전위 순회, 후위 순회, 중위 순회이다. 이는 Tree에서의 traversal인데, 전위는 노드 왼쪽에서 방문하고, 중위는 노드 아래에서 만나고, 후위는 노드 오른쪽에서 만난다. 이를 그림으로 보면 이해하기 쉽다. 1️⃣ PreOrder Traversal 2️⃣ InOrder Traversal 1️⃣ PostOrder Traver…

기존에는 Python으로 알고리즘 문제를 풀어왔지만, 이번 포스팅부터 JAVA로 전환하고자 하고자 합니다. 그 이유로는 크게 두 가지 이유가 존재합니다. 1️⃣ Web BackEnd 개발자. 기존에는 원래 많이 사용했던 Python이 익숙해 알고리즘 문제 풀 때 자연스럽게 Python을 사용했습니다. 하지만, 본격적으로 Web BackEnd 개발자를 목표로 공부하며 자바에 익숙해지고 있었습니다. 2️⃣ SSAFY 8기 참여 SSAFY 8기에 Java Web 과정에 참여하게 되면서 완전히 전환을 하고자 합니다. 공부하고 있는 Framework도 Spring이고 취업 또한, Java 기반의 Spring Framework를 사용하는 회사에 지원할 예정이기 때문에, Python 보다는 회사에서 사용하는 언어인 Java로 코딩테스트를 보는 것이 아무래도 조금이나마 유리하다고 생각되어 전환하고자 합니다. 아직은 Python에 비해 library 도 불편함이 많은 것 같고, 자료구조의 시간…

BOJ 1102 - 발전소 Gold-Ⅰ 이 문제는 BOJ 문제입니다. 문제 출처 : 발전소 💥 문제 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다. 발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다. 적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 값…

BOJ 1194 - 달이 차오른다, 가자. Gold-Ⅰ 이 문제는 BOJ 문제입니다. 문제 출처 : 달이 차오른다, 가자. 문제 지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다. 민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다. 하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다. 영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다. 민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미…

BOJ 17471 - 게리맨더링 Gold-Ⅳ 이 문제는 BOJ 문제입니다. 문제 출처 : 게리맨더링 문제 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다. 아래 그림은 6개의 구역이 있는 것이고…

SWEA 14362 - 무한 로봇 D-Ⅳ 이 문제는 SWEA 문제입니다. 문제 출처 : 무한 로봇 🔥 주의할 점 k번째로 명령을 수행한 직후의 위치를 라고 할 때, 는 모든 좌표를 의미한다. 로봇이 이동을 마치고 난 후의 점이 아닌 이동 중 마주한 모든 정수 좌표들을 의미한다. 💥 How to Solve? 결과부터 말하자면, 테스트 케이스는 125개, 최대 움직임은 2500회이다. 내가 구현한 방법은 움직임이 Worst Case인 경우 총 4번을 반복해야하니 10000회 이루어지고, 모든 TC가 10000회 이루어진다해도 125만회로 제한 시간 3초 이내에 해결할 수 있다고 판단해 단순 구현 방법으로 해결했다. ‼ Point ‼ 우선 용어 몇 가지를 정의하고 시작한다. | ➡ | ⬇ | ⬅ | ⬆ | ➡ | 움직임 : 로봇이 움직인 방향을 기록한 데이터 초기 방향 : Right 시작 방향 : 첫 움직임 방향 - ex) RS 라고 한다면 맨 처음 Right에서 오른…

SWEA 4111 - 무선 단속 카메라 D-Ⅳ 이 문제는 SWEA 문제입니다. 문제 출처 : 무선 단속 카메라 🔥 Point 이 문제의 핵심은 Kruskal 알고리즘에서 아이디어를 떠올렸다. Kruskal 알고리즘은 MST(Minimum Spanning Tree)를 만들기 위한 알고리즘 중 하나이다. MST란 최소 비용으로 만들 수 있는 Spanning Tree(신장 트리)를 찾는 알고리즘이다. 🌟 MST 찾기 위해서 Kruskal 알고리즘은 모든 간선 중 가장 비용이 낮은 간선들부터 제거하며 해당 간선으로 이어져 있는 노드들끼리 합쳐주는 것 이다. 이를 이 문제에 적용해 해결할 것이다. 💥 How to Solve? 수신기는 모든 카메라들을 포함하고 있어야 한다. 이를 반대로 생각해봤다. 모든 카메라에 하나의 수신기들이 배당되어 있고, 가장 붙어있는 카메라들을 하나의 수신기가 담당하도록 한다. 이해를 위해 그림으로 살펴보자. 1️⃣ 최초에는 모든 카메라에 수신기를 부여…

SWEA 4408 - 자기 방으로 돌아가기 D-Ⅳ 이 문제는 SWEA 문제입니다. 문제 출처 : 자기 방으로 돌아가기 💥 How to Solve? 1 3 5 7 .. .. .. .. 397 399 2 4 6 8 .. .. .. .. 398 400 1️⃣ 좌표 압축 이 문제는 1-2, 3-4, 5-6, … 399-400 이 각자 한 쌍을 이룬다. 즉 1번 방에서 3번 방으로 이동하고, 4번 방에서 8번방으로 이동한다면 3-4 복도에서 겹친다는 결과가 나온다. 이를 이용해서 1-400의 좌표를 1-200 좌표로 압축했다. 홀수는 (odd+1)//2, 짝수는 (even//2) 를 통해서 1,2 좌표를 1로 압축하는 작업을 수행한다. 2️⃣ Line Sweeping 입력으로 들어온 구간에 이동하는 횟수를 기록한다. 즉, 입력으로 들어온 구간에 +1을 해준다. 이 문제는 같은 방이 중복으로 등장하지 않고, 들어갔다 다시 나오는 작업들이 없기 때문에, 이동 횟수를 +1 씩 해주면 각 …

SWEA 6959 - 이상한 나라의 덧셈게임 D-Ⅳ 이 문제는 SWEA 문제입니다. 문제 출처 : 이상한 나라의 덧셈게임 💥 How to Solve? 이 문제는 1000자리 수까지 계산해야하기 때문에, 수 자체로 접근하게 되면 오류가 발생할 가능성이 매우 높다. 처음에는 서로 최선의 수를 선택한다고 했기 때문에 Brute-Force 를 생각했다. 하지만 1000의 자리를 모두 고려하기에는 재귀의 깊이가 너무 깊어질 것 같다. 그렇다면 남은 방법은 어떻게 효율적으로 판단할 수 있을지 고민해야한다. 해결하지 못해 문제 아래 댓글을 통해 힌트를 얻고 쉽게 해결했다. 123 이런 수가 있다고 한다면, 12를 합치면 33, 23을 합치면 15가 나온다. 두 자리의 합이 10을 넘지 않는 이상 자리 수가 줄어들게 되어있다. 그리고 다시 33이나 15를 합치게 되면 6으로 총합은 변하지 않는다. 78 을 살펴보자. 78을 합치면 15가 된다. 자리수는 줄어들지 않는다. …

SWEA 10762 - 사탕 나누기 D-Ⅳ 이 문제는 SWEA 문제입니다. 문제 출처 : 사탕 나누기 💥 How to Solve? 편의상 동원이를 형이라 하고 그 동생을 동생이라고 칭한다. 형은 동생보다 많은 사탕을 가지고 싶어하고 동생은 사탕 수를 XOR 연산을 통해서 계산한다. 각 사탕 봉지안의 사탕 수를 이라고 할 때, 동생 기준으로는 이런 식이 나와야 한다. 우선 이 문제의 핵심은 XOR 연산자이다. XOR 연산자의 경우 비트간 서로 다른 경우에만 1이 된다. 즉 위와 같은 연산, 의 결과가 나온다. XOR 연산의 특징 하나를 알면 굉장히 쉽게 해결할 수 있다. XOR 연산은 이라면 위와 같은 특징을 이용한다면 굉장히 쉽게 해결할 수 있다. 주어진 모든 수들을 XOR 한 결과를 통해 그 결과가 0이라면 동생에게 최소 사탕 봉지 딱 하나만 넘겨주고 나머지는 형이 독식한다해도 동생의 기준으로는 공평한 배분이 된다. ✨ Python Code 💥 끝!! ✨ …

SWEA 4699 - 콩순이의 가장 싼 팰린드롬 D-Ⅳ 이 문제는 SWEA 문제입니다. 문제 출처 : 콩순이의 가장 싼 팰린드롬 Palindrome 이란? 팰린드롬이란 문자열, DP 문제에서 종종 접할 수 있는 문제이다. 팰린드롬을 가장 쉽게 표현하자면 거꾸로 해도 똑같은 문자라고 할 수 있다. 예를 들어, ABBA 와 같이 거꾸로 해도 똑같은 문자를 의미한다. How to Solve? 처음에는 문자를 제거하고 삽입하는 모든 경우를 탐색하면서 팰린드롬이 완성됐다면 Cost 값을 저장해두고 해당 Cost보다 큰 경우는 바로 탐색 종료하는 방식의 BackTracking 방식으로 구현했다. 하지만 이 문제의 Stack 메모리 제한이 있기에 재귀로 해결하기 어렵다. 따라서 다른 방식의 접근이 필요하다. 앞서 Palindrome을 설명하면서 DP에서 자주 나온다고 설명했다. 따라서 이 문제에서도 DP를 활용한 접근 방법을 알아본다. 🔥 DP 핵심은 가장 인접한 두 글자부터 팰린…

SWEA 10805 - 야바위 D-Ⅳ 이 문제는 SW Expert Academy 문제입니다. SWEA 10805 - 야바위 문제 동호는 공과 N개의 컵을 가지고 야바위를 하고 있다. N개의 컵은 모두 구별이 가능하고, 일렬로 늘어서 있다. 처음에 왼쪽에서 첫 번째 컵에 공을 넣어놓는다. 그리고 앞으로 Q번 두 컵의 위치를 바꾸는데, i번째에는 왼쪽에서 Ai번째 컵과 왼쪽에서 Bi번째 컵의 위치를 바꾼다. 동호는 공이 어떤 컵에 있는지 맞출 수 없도록 하기 위해 정확히 한 번 속임수를 쓰려고 한다. 속임수는 현재 공이 들어있는 컵이 왼쪽에서 i번째 컵이라고 할 때, 왼쪽에서 i-1번째 컵이나 왼쪽에서 i+1번째 컵으로 공을 순간 이동시키는 것이다. 이 속임수는 컵을 섞는 도중이 아니라면, 어떤 시점에도 가능하다. 입력 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 N,Q (1 ≤ N, Q ≤ 105)가 공백 하나로 구분되어 주…

BOJ 1941 - 소문난 칠공주 Gold Ⅲ BOJ 1941 - 소문난 칠공주 문제 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다. 그러나 생존을 위해, ‘이다솜파’가 …

BOJ 9015 - 정사각형 Gold Ⅰ BOJ 9015 - 정사각형 문제 평면 위에 N개의 점이 주어졌을 때, 가장 큰 정사각형의 넓이를 구하여라. 문제 그림 입력 첫째 줄에 테스트케이스의 개수 T가 주어진다. 각 테스트케이스의 첫째 줄에는 점의 개수 N(4 ≤ n ≤ 3,000)이 주어지고, 이어서 N개의 줄에는 점의 x좌표와 y좌표가 주어진다. 모든 좌표는 -10000 이상 +10000이하의 정수이다. 같은 위치의 점이 여러 번 주어지는 경우는 없다. 출력 각 테스트 케이스마다 가장 큰 정사각형의 넓이를 한 줄에 하나씩 출력한다. 단, 정사각형이 없는 경우 0을 출력한다. How to Solve? 점 4개를 선택해 정사각형 여부 확인하는 방법은 로 불가능하다. 그래서 처음 생각했던 방법은 대각선 두 개를 선택해 두 대각선의 길이가 같고, 두 대각선의 기울기를 a1, a2라 했을 때, 즉 직교한다는 성질을 이용해 해결하려고 했다. 하지만 이 또한, …

BOJ 2140 - 지뢰찾기 Gold Ⅴ BOJ 2140 - 지뢰찾기 문제 지뢰찾기는 N×N에서 이뤄지는 게임이다. 보드의 곳곳에는 몇 개의 지뢰가 숨겨져 있고, 지뢰가 없는 칸에는 그 칸과 인접(상하좌우 및 대각선)해 있는 8개의 칸들에 몇 개의 지뢰가 숨겨져 있는지에 대한 정보가 주어진다. 게이머는 게임을 진행하면서 보드의 칸을 하나씩 열게 된다. 만약 그 칸에 지뢰가 있다면 게임이 끝나고, 없는 경우에는 그 칸에 적혀있는 숫자, 즉 그 칸과 인접해 있는 8개의 칸들 중 몇 개의 칸에 지뢰가 있는지를 알 수 있게 된다. 이 문제는 보드의 테두리가 모두 열려있고, 그 외는 모두 닫혀있는 상태에서 시작한다. 예를 들어 다음과 같은 경우를 보자. 1 1 1 0 0 2 # # # 1 3 # # # 1 2 # # # 1 1 2 2 1 0 #는 닫혀있는 칸을 나타낸다. 이러한 보드가 주어졌을 때, 닫혀있는 칸들 중 최대 몇 개의 칸에 지뢰가 묻혀있는지 알아내는 프로그램을 작성하시오. …

BOJ 17947 - 상남자 곽철용 Gold Ⅰ BOJ 17947 - 상남자 곽철용 문제 우리의 우상 곽철용은 화투로 노름을 하는 것을 매우 좋아한다. 이번에 그는 지인들과 함께 새로운 게임을 해보려고 한다. 게임은 M명의 참가자로 진행되며, 4 × N장의 카드를 가지고 한다. 카드에 적힌 숫자는 1부터 4 × N까지의 수이며, 중복되는 숫자가 적힌 카드는 존재하지 않는다. M명의 참가자들은 우선 4 × N장의 카드에서 각각 2개의 카드를 뽑아서 버린다. 그리고 다시 M명의 참가자들은 각각 2개의 카드를 뽑는다. 게임의 승부는 두번째에 뽑은 두 장의 카드에 적힌 숫자에 따라 결정된다. 각 참가자의 점수는 두 장의 카드에 적힌 숫자를 K로 나눈 나머지의 차이다. 곽철용은 두번의 카드 뽑기 후, 초조한 마음에 자신이 이 게임에서 이길 수 있는지 매우 궁금해졌다. 그래서 자신보다 점수가 높은 사람들이 최대 몇 명인지 알고자 한다. 여러분들이 상남자 곽철용의 초조한 마음을 풀어주도록 …

BOJ 23291 - 어항정리 Platinum Ⅴ BOJ 23291 - 어항정리 💥 Rule 1. 물고기 추가 - add_fish() 가장 적은 수의 물고기가 담긴 모든 어항에 물고기 한 마리씩 추가한다. 배열을 순회하면서 min 값을 갖는 인덱스를 모두 저장해둔다. 해당 인덱스에 해당하는 어항에 물고기 한 마리씩 추가한다. ✨ Python Code 2. 어항 쌓기 - stack_bowl() 세로 배열과 가로 배열로 구분해서 관리할 것이다. 모든 세로 배열의 끝에서부터의 원소들과 가로 배열의 첫 번째부터의 원소들이 짝을 이뤄 새로운 하나의 세로 배열을 생성하게 된다. 세로 배열 하나의 길이가 가로 배열의 길이보다 커질때까지 어항을 쌓을 수 있다. 이해를 위해 그림을 추가한다. ✨ Python Code 3. 물고기 조정하기 - balance() 각 어항들의 인접한 어항들간의 차이를 줄이는 과정이다. 인접한 어항들간의 차이를 diff 라 하고, diff를 5로 나…

BOJ 9320 - 금고열기 Gold Ⅲ BOJ 9320 - 금고열기 문제 비밀 요원 상근이는 시리아의 화학 무기에 대한 정보를 보관하고 있는 금고를 열려고 한다. 금고를 열려면 금고에 암호를 입력해야 한다. 암호는 숫자 네 개로 이루어져 있다. 상근이는 시도해야 하는 암호의 목록을 가지고 있다. 목록에는 매우 많은 암호가 적혀있기 때문에, 암호가 될 수 없는 것을 미리 지우려고 한다. 올바른 암호는 24 조건을 만족한다. 암호를 이루는 수 네 개 사이에 덧셈, 뺄셈, 곱셈, 나눗셈, 괄호를 적절히 삽입해서 24를 만들 수 있을 때, 그 암호를 24 조건을 만족한다고 한다. 예를 들어, (4, 7, 8, 8)은 (7-8/8)*4 = 24이기 때문에, 24 조건을 만족한다. 하지만, (1, 1, 2, 4)나 (1, 1, 1, 1)과 같은 암호는 24 조건을 만족하지 않는다. 따라서, 이러한 암호는 시도해볼 필요가 없다. 가능한 암호가 모두 주어졌을 때, 24 조건을 만족하는지 안…

문제 풀이에 앞서 Segment Tree에 대한 설명과 어떤 상황에 왜 사용하기 좋은지 먼저 설명하도록 한다. baekjoon님이 작성하신 글을 보고 정리한 내용입니다. ✨ Segment Tree 왜 사용할까? 구간 합과 변경을 반복 한다면? 1)구간 left, right가 주어질 때, S의 값을 구하라. 2) i번째 수를 변경하라. 위의 1), 2) 과정을 반복한다면 loop 문을 통해 1) 식을 해결할 경우. S를 구하기 위해서 O(N) Time. 값을 변경하기 위해서 O(1) Time 총 M번이 반복된다면 O(NM) Time. DP를 이용해 해결할 경우 S를 구하기 위해서는 O(1) Time ex) l = 2, r = 5, then S = DP[5] - DP[1] 로 O(1) time 해결 가능하다. 값을 변경하게 된다면 DP도 갱신이 되어야 한다. 따라서 O(N) Time 총 M번 반복시 O(NM) Time. 이렇듯 loop문이나 DP로 해결하게 된다면 O(NM) T…