만년다딱2의 개인공간

1. 문제링크 https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 2. 접근방법 우주선은 3개의 방향으로 나올 수 있다 즉 dp[n][m] 사이즈에서 나올수있는 3가지 방향 [3] 까지 해서 3차원 배열로 생각해주자 제일 오른쪽과 제일 왼쪽은 각 대각선별로 올 수 없다! 이 예외처리를 해주어야 한다!! 중요!! 이것이 다되면 제일 밑에 도착한 값들 중 최소값을 찾아주면 종료~! 3. 코드 import java..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 오늘도 알고리즘! 쉬운 계단 수 라는 문제이다. 인접한 모든 자리 수의 차이가 1이 나는 수를 계단수라고 하고 길이가 N인 계단 수를 찾는 문제이다. 다이나믹 프로그래밍으로 풀 수 있는 문제이다. DP 배열을 2차원의 공간으로 생각하고 dp[ 길이 ] [ 0 ~ 9 ] 까지의 공간으로 반복문을 돌면서 계산해 나갈 수 있다. 첫번째 0을 제외한 첫 자리수에 대한 DP값은 1이다. 1, 2, ... , 9 이후 10의 자리 수 부터는 0으로 시작하는 수를 제외하곤 그 전 자리 수의 -1, +1 의 dp값을 더하면 ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 오늘도 알고리즘! 오늘은 간단한 DP문제를 복습한번 해보았습니다. 정수삼각형이라는 문제인데요 위에서 얻을 수 있는 경로의 최대 합을 구하는 문제입니다 데이터 입력을 받으면서 현재 내 윗줄의 왼쪽과 내 윗줄의 바로 위쪽중 큰 값을 더해가면서 그중 최대값을 찾는 문제인데요 간단한 DP연습을 해보기 좋은 문제라고 생각합니다. 오늘도 코딩! 오늘도 알고리즘 파이팅! import java.util.Scanner; public class Main { public static vo..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 오늘도 알고리즘! 직전에 포스팅한 파이프 옮기기 1 문제를 DP 방식으로 풀어보았습니다. 놓을 수 있는 위치에 관한 값들만 고려한다면 입력받으면서도 빠르게 처리할 수 있기때문에 속도에서 확연한 차이가 보입니다. 특정 파이프를 놓을 수 있는 위치에 대해서 DP 값을 본다면 쉽게 풀 수 있는 문제입니다. import java.util.StringTokenizer; import..