2JINISHAPPY 2JINISHAPPY

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

www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 로봇이 동서남북으로 N번 움직일 수 있다고 할 때, 이동 경로가 단순할 확률(이미 방문한 곳을 방문하지 않을 확률)을 구하는 문제이다. N이 14 이하의 자연수이기 때문에, 최대 4^14(268,435,456)가지의 이동 경우의 수가 나온다. 즉, 1억번 이하이므로 모든 경우에 대해 조사하면서 단순한지 아닌지 검사해주었다. 백트래킹을 이용해서 특정 좌표의 방문/미방문을 갱신해주었고, 서로 다른 좌표를 N개 ..

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/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의 최대 연결..