💬 문제 설명다음과 같이 4개의 정사각형을 이용하여 변끼리 연결되도록 만든 모양을 '테트로미노'라고 한다.`N` x `M` 종이에서 테트로미노 모양에 맞는 칸 중에서 그 칸에 적힌 수들의 합이 최대가 되는 경우를 찾고자 한다.📌 핵심 포인트4 ≤ `N`, `M` ≤ 500이므로 `N` x `M`은 최대 250,000,테트로미노 모양을 만드는데 필요한 칸수는 4개이므로,각 칸을 순회하면서 테트로미노 모양에 맞는 칸을 확인하면,250,000 x 4^3 = 16,000,000번 정도의 연산이 발생하므로(4방향 탐색, DFS 깊이가 3(시작 칸 제외) → 4^3)→ DFS을 활용한 완전탐색으로 가능한 모든 테트로미노 배치를 탐색할 수 있음또한, DFS에서 백트래킹을 활용해서 중복 연산을 줄일 수 있음(갈래가..

💬 문제 설명`N` x `M` 크기에 지도가 있고 `(x, y)` 칸에 주사위가 위치한다. 주사위의 6면은 0으로 초기화되어 있다.주사위를 동, 서, 남, 북 방향으로 굴려서 이동시킬 때, 주사위의 바닥면과 맞닿는 지도칸에 적힌 수가 0이면 주사위의 바닥면에 적힌 값을 지도칸에 복사한다. 지도칸에 0이 아닌 수가 적혀 있다면 그 수를 주사위 바닥면으로 복사하고 0으로 만든다.주사위를 굴릴 때마다 주사위의 윗면에 적힌 수를 출력한다.단, 주사위가 지도 바깥으로 나가게 되는 경우는 무시하며 출력도 하지 않는다.📌 핵심 포인트주사위의 6면에 적힌 값들은 저장하는 1차원 배열 정의dice[6]: 각 인덱스는 주사위의 위치를 표현(0: 윗면, 5: 바닥면) 13 0 2 (5) 4 5동, 서, 남,..

💬 문제 설명뱀이 이동하면서 사과를 먹으면 몸의 길이가 길어지고, 벽이나 자신의 몸과 만나면 끝나는 게임을 진행한다.특정 시간에서 회전하는 조건이 주어질 때, 몇 초 후에 게임이 끝나게 되는지 구하는 문제이다.📌 핵심 포인트뱀은 머리와 꼬리가 있고 몸의 길이가 늘어나고 줄어들 수 있다.→ Deque 활용(몸이 길어질 때 머리 쪽을 늘리고, 몸이 짧아질 때는 꼬리 쪽을 줄인다)(꼬리/뒤)---------Deque--------->(머리/앞) 뱀은 머리가 향하는 방향으로 이동한다.→ 이동할 방향이 정해져 있으므로 BFS/DFS가 아닌 시뮬레이션방향 정보에 따라 머리 방향을 회전한다.L: 왼쪽으로 90도 회전(반시계 방향)D: 오른쪽으로 90도 회전(시계 방향)💫 문제 풀이뱀의 몸통 위치 정보를 덱으로 ..

💬 문제 설명보드 위에 빨간 구슬(`R`)과 파란 구슬(`B`)이 놓여 있다. 상/하/좌/우 중 한 방향으로 기울이면 두 구슬이 동시에 해당 방향으로 굴러간다. 이때 빨간 구슬만 구멍에 넣으려고 할 때 보드를 움직이는 횟수를 10번 이하로 하는 최소 횟수를 구한다.📌 핵심 포인트두 구슬은 동시에 이동한다.이동 순서에 따라 결과가 달라질 수도 있다.두 구슬이 같은 칸에 도착할 수 있다고 가정하여, 충돌 보정 로직이 필요하다→ 위 상황을 가능하게 한 이유는 두 구슬이 동시에 구멍에 들어가는 경우도 생각해야 하기 때문에!파란 구슬이 구멍에 빠지는 경우는 무조건 실패→ 따라서 빨간 구슬보다 먼저 구멍 도착 여부를 확인한다.💫 문제 풀이1. 상, 하, 좌, 우 방향으로 두 구슬 굴리기`move()`: 구슬의..

💬 문제 설명서로 다른 `K`개의 소수가 주어진다.이 소수들을 중복 사용 가능하여 곱해 만들 수 있는 수들을 오름차순으로 나열할 때 `N`번째 수를 구하는 문제이다.📌 핵심 포인트단순히 모든 가능한 수를 만들어서 정렬한 뒤 `N`번째를 고르면 메모리 초과 발생 🚨곱으로 만들어지는 수의 개수는 기하급수적으로 증가하고, 중복되는 값도 매우 많이 생성되기 때문이다.따라서 이 문제는 필요 없는 수를 아예 만들지 않는 것이 핵심!💫 문제 풀이1. PriorityQueue(MinHeap) 활용어떤 수 `a`, `b`가 있을 때, `a^2`이 `a x b`보다 큰지 일일이 판별하기 어렵기 때문에, 이런 문제는 힙(Heap)을 떠올려줘야 한다. 항상 작은 수부터 꺼내기 위해 활용한다.힙을 사용하기로 했다면 이제..

💬 문제 설명`N` 개의 추들이 주어질 때, 이 추들을 이용해 측정할 수 없는 가장 작은 양의 정수 무게를 구하는 문제이다.📌 핵심 포인트모든 무게를 직접 만들어보는 방식(부분집합 탐색)은 시간 초과"어떤 무게를 만들 수 있는가?"보다 "어디까지 연속으로 만들 수 있는가?"를 생각해야 한다.💫 문제 풀이이 문제는 그리디 알고리즘으로 해결할 수 있다.현재까지 `1 ~ X` 까지의 모든 무게를 만들 수 있다고 하자. (`X`는 만들 수 있는 값의 상한)이때 다음 추의 무게가 `w` 일 때,`w ≤ X + 1`이라면 → `1 ~ (X + w)` 까지 연속으로 만들 수 있다.(`w = X + 1` 이면 나머지 추를 사용하지 않고 `w` 만 사용해서 `X + 1`를 만듦) 혹은`w > X + 1`이라면 → ..