2JINISHAPPY 2JINISHAPPY

www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 삼성 A형 기출인 사다리 조작 문제 시간을 줄일 수 있는 분기가 많기에 백트래킹 연습에 좋은 문제라고 생각한다. 사다리는 0개~3개를 설치할 수 있다. 따라서 4번의 반복문을 통해 해당 탐색에서 놓을 총 사다리 수를 정하고 백트래킹 루틴을 돌려 주었다. 까다로웠던 점은 해당 stage에 사다리 설치를 완료한 뒤 중복 체크를 막기 위한 다음 stage 선정이 조금 어려웠다. 그래서 처음엔 행 - 열 순서로 검사..

www.acmicpc.net/problem/16931 16931번: 겉넓이 구하기 크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다. 종이의 각 칸에 놓인 정육면체의 개수가 주어 www.acmicpc.net 백준의 겉넓이 구하기 문제 기하적인 문제이다 각 칸의 넓이를 1이라 했을 때, 도형의 겉넓이를 구하는 문제이다 이 때, 그림의 흰색 칸은 위에서 투시했을 때의 위쪽 면의 겉넓이이다. 밑에서 봤을 때에도 동일하므로 초기의 겉넓이 값은 N*M*2이다 그리고 옅은 주황색 면을 보면, 요철이 많지만 앞에서 투시해서 봤을 때 반대편에서 봤을 때랑 겉넓이가 같음을 알 수 있다. 따라서 옅은 주황색 면의 겉넓이..

www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 수열이 있을 때, 각 원소에 대해 오큰수를 구하는 문제 오큰수란? 해당 원소를 Ai라 할 때 Ai의 오른쪽에 위치한 원소들 중 index가 가장 작으면서 Ai보다 큰 원소를 나타낸다 예제에 대해, [3 5 2 7]을 마지막 원소부터 보면 - 7: 오른쪽에 원소가 없으므로 -1 - 2: 바로 오른쪽에 7이 2보다 크므로 7 - 5: 한 칸 건너뛰어서 7이 5보다 크므로 7 - 3: 7이 가장 크지만 5가 7보다 왼쪽에 있으므로..

www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 전형적인 DP문제인 구간합 구하기이다 !! 1. 문제 정의 (x1, y1)부터 (x2, y2)까지의 직사각형 영역에 있는 element들의 합을 구한다 2. Subproblem & Recurrence (0,0) ~ (X2,Y2)까지의 구간합은 (X1-1,Y2)의 구간합+ (X2,Y1-1)의 구간합 - (X1-1,Y1-1)의 구간합으로 나타낼 수 있다(아래의 그림 참조)..

www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 미로 만들기 문제 2차원 배열에서의 최단거리 문제이다. 벽부수고 이동하기와 미로만들기처럼 벽(cost가 높은 좌표)를 최소화해서 목적지에 도착하기 위해서는, 가중치 그래프의 최단거리를 이용해야 한다 따라서 2차원 배열에 다익스트라 알고리즘을 적용하면 문제를 해결할 수 있다 문제에서는 흰색(지나갈 수 있는 곳)을 1, 검은색을 0으로 해줬는데 입력받은 뒤 이를 완전히 뒤집고 다익스트라 알고리즘을 통해 (N,N)으로 갈 ..

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. 문제 정의 N줄에 걸쳐 3개의 숫자 중 최대 점수를 얻을 수 있는 숫자를 선택한다. 단, 이전에 선택했던 열과 인접한 열에 있는 숫자만 선택 가능하다. 2. Recursion&Subproblem K-1번째 줄에서 1번을 선택했다면 K번째 줄에서 1, 2번 중 큰 숫자를 선택한다 K-1번째 줄에서 2번을 선택했다면 K번째 줄에서 1,2,3번 중 큰 숫자를 선택한다 K-1번째 줄에서 3번을 선택했다면 K번째 줄에서 2,3번..

www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1. 문제 정의 좌표 평면 내의 1로 이루어진 가장 큰 정사각형의 넓이를 출력한다 이 때, 넓이를 구하기 위해 가장 큰 정사각형의 한 변의 길이를 구한다 위와 같은 그림에서 최대 정사각형의 한 변의 길이는 2이므로, 답은 4이다 2. Subproblem&Recursion 특정 좌표를 오른쪽아래 꼭지점으로 정사각형의 길이를 구한다고 할 때, 이 좌표의 북, 서, 북서쪽 좌표는 반드시 1이어야 한다. 그리고 좌표가 아래와 같을 경우, 0111001 -> 0111001 0111001 -..

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 이차원 배열을 이용하는 DP문제 욕심쟁ㅇㅣ 판다🐼 1. 문제 정의 이차원 배열에서 특정 칸에서 연결된 상하좌우의 칸이 인접하다고 할 때, 인접한 칸이 현재 칸보다 숫자가 큰 최대 연결 회수 구하기 2. Recursion & Subproblem 4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8 위의 예시에서, 5의 최대 연결 수는 5-11-15로 3번이다. 이 때, 2의 최대 연결..