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

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 씩 해주면 각 …

문제 풀이에 앞서 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…