문제 n×n 크기의 격자 정보가 주어졌을 때, (1, 1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (n, n)으로 간다고 했을 때 거쳐간 위치에 적혀있는 수들 중 |최댓값-최솟값|을 최소로 만드는 프로그램을 작성해보세요. 예로 다음 그림을 살펴봅시다 입력 형식 첫 번째 줄에는 n이 주어집니다. 두 번째 줄부터 n개의 줄에 걸쳐 각 행에 해당하는 n개의 정수 값이 공백을 사이에 두고 주어집니다. 1 ≤ n ≤ 100 1 ≤ 주어지는 숫자 ≤ 100 출력 형식 가능한 경로상의 |최댓값-최솟값| 중 최솟값을 출력합니다. 입출력 예제 예제1 입력: 3 1 2 3 5 4 6 7 1 2 출력: 3 예제2 입력: 4 20 30 51 30 22 10 12 1 10 25 35 21 34 36 20 20 출력: 21 ..

문제 n×n 크기의 격자 정보가 주어졌을 때, 시작점을 적절하게 잡아 상하좌우로 인접한 칸으로 계속 칸에 적혀있는 정수값이 커지도록 이동한다고 했을 때 밟고 지나갈 수 있는 최대 칸의 수를 구하는 프로그램을 작성해보세요. 입력 형식 첫 번째 줄에는 n이 주어집니다. 두 번째 줄부터 n개의 줄에 걸쳐 각 행에 해당하는 n개의 정수 값이 공백을 사이에 두고 주어집니다. 1 ≤ n ≤ 500 1 ≤ 주어지는 숫자 ≤ $10^9$ 출력 형식 가능한 경로의 숫자들 중 최솟값의 최댓값을 출력합니다. 입출력 예제 예제1 입력: 3 2 2 1 3 1 2 4 1 2 출력: 3 예제2 입력: 3 5 1 3 6 1 4 7 2 3 출력: 4 예제 설명 백트래킹으로 풀거나 DP로 풀면 된다. 백트래킹 방법 import sys ..

https://www.codetree.ai/missions/2/problems/maximin-path-in-square/description 유사한 문제: 정수 사각형 최댓값의 최소 ⭐⭐⭐[코드트리] 정수 사각형 최댓값의 최소 https://www.codetree.ai/missions/2/problems/minimax-path-in-square/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지 hyundoil.tistory.com 문제 N×N 행렬이 주어졌을 때, (1,1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (N,N)으로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자들 중 최솟값을 최대로 하는 프로..

문제 N×N 행렬이 주어졌을 때, (1,N)에서 시작하여 왼쪽 혹은 밑으로만 이동하여 (N,1)로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자의 합을 최소로 하는 프로그램을 작성해보세요. 입력 형식 첫째 줄에는 N이 주어집니다. 두 번째 줄 부터 N개의 줄에 각각 각 행에 해당하는 N개의 정수 값이 공백을 사이에 두고 주어집니다. 1≤N≤100 1≤ 행렬에 주어지는 숫자 ≤1,000,000 출력 형식 가능한 최소 합을 출력합니다. 입출력 예제 예제1 입력: 3 5 2 1 1 9 1 1 8 9 출력: 10 오른쪽 위에서 왼쪽 아래로 한칸씩 감 최대 합 import sys sys.stdin=open('input1.txt','r') if __name__=="__main__": n=int(input()) boa..

문제 N×N 행렬이 주어졌을 때, (1,1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (N,N)으로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자의 합을 최대로 하는 프로그램을 작성해보세요. 입력 형식 첫째 줄에는 N이 주어집니다. 두 번째 줄 부터 N개의 줄에 각각 각 행에 해당하는 N개의 정수 값이 공백을 사이에 두고 주어집니다. 1≤N≤100 1≤ 행렬에 주어지는 숫자 ≤1,000,000 출력 형식 가능한 최대 합을 출력합니다. 예제1 입력: 3 1 2 3 3 2 1 4 2 1 출력: 11 예제2 입력: 3 1 3 2 3 4 5 4 2 1 출력: 14 백트래킹과 DP 문제인거 같다. 그러나 백트래킹의 경우도 중복되는 계산이 발생하므로 DP로 푸는것이 가장 최적이다. 백트래킹 방법 1 import s..

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog 1149번: RGB거리 문제 보러가기  1149번: RGB거리첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나www.acmicpc.net 시간 제한: 0.5초 메모리 제한: 128 MB  문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초..