먹여살릴냥꽁이가있습니다.

문제

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

입력

출력

D (탈출 할 수 없다면, -1을 출력한다.)

예제

코드

풀이 방법

미로에서 탈출할 수 있는 가장 빠른 경로 거리를 구하는 문제였습니다. 미로 안에는 벽을 길로 만들 수 있는 지팡이가 존재하기 때문에 3차원 배열을 이용해 문제를 풀었습니다. 지팡이는 한 번만 사용할 수 있기 때문에 만약에 지팡이를 사용하지 않았다면 길 혹은 벽으로 이동할 수 있고, 반대로 지팡이를 이전에 사용했더라면 길인 경우에만 이동할 수 있도록 해주었습니다. 그리고 탈출 위치에 도착했다면 거리를 리턴해주고 출력해주었습니다.

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

출력

각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.

예제

코드

풀이 방법

통나무들로 만들 수 있는 최소 난이도를 구하는 문제였습니다. 맨 처음 통나무와 맨 마지막 통나무는 인접해 있으므로 정렬을 해서 통나무를 놓으면 맨 처음 통나무와 맨 마지막 통나무의 높이 차이가 최대로 되기 때문에 먼저 통나무 높이를 오름차순으로 정렬 후, 맨 앞에 하나 맨 뒤에 하나 그다음 앞에 하나 그다음 뒤에 하나 이런 식으로 앞 뒤 앞 뒤에 넣어줌으로써 높이 차이를 최소로 할 수 있었습니다. 통나무들을 다 세운 뒤 각 인접해 있는 통나무들의 높이차를 구해 가장 높이차가 큰 난이도를 출력해주었습니다.

문제

윌리암슨수액빨이딱따구리 세 식구가 정보섬에 올라왔다!

세 윌리암슨수액빨이딱따구리는 정보섬 2층 어딘가에 모여 앉아 쉬고 있었는데, 저 멀리 청국장과 스시와 맥앤치즈가 있는 것을 발견했다! 아빠는 청국장, 엄마는 스시, 아이는 맥앤치즈가 먹고 싶다. 그래서 이 셋은 현위치로부터 가장 가까운 음식을 먹으러 가기로 했다.

정보섬 2층은 An×m의 격자로 표현된다. 어떤 Ai,j가 0이면 빈 복도여서 지나갈 수 있고, 1이면 장애물로 막혀 지나갈 수 없다. 윌리암슨수액빨이딱따구리 식구는 2, 청국장은 3, 스시는 4, 맥앤치즈는 5이다. 윌리암슨수액빨이딱따구리는 단위 시간마다 한 칸, 상하좌우로 움직일 수 있다. 2, 3, 4, 5는 장애물이 아니므로 지나갈 수 있다. 격자 밖으로는 나갈 수 없으며 시작점으로부터 시작점까지의 거리는 0이다. 시작점은 윌리암슨수액빨리딱따구리의 위치, 즉 2의 위치이다.

과연 윌리암슨수액빨이딱따구리 식구는 어떤 음식에 더 빨리 도착할 수 있을까?

입력

첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106)

이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다.

2, 3, 4, 5는 반드시 하나씩 존재하며 2, 3, 4, 5가 아닌 나머지는 0 또는 1이다.

출력

첫째 줄에 "TAK"(폴란드어로 YES를 의미)을 출력하고, 둘째 줄에 현위치에서 가장 빨리 도착할 수 있는 음식까지의 최단 거리를 출력한다.

아무 음식도 먹을 수 없으면 "NIE"(폴란드어로 NO를 의미)를 출력한다. 이외의 출력은 하지 않는다.

TAK과 NIE를 출력할 때 따옴표는 출력하지 않으며 반드시 대문자로 출력한다.

예제

코드

풀이 방법

현재 위치에서 가장 빨리 도착할 수 있는 음식까지의 최단 거리를 구하는 문제였습니다.

딱따구리의 현재 위치 정보를 큐에 넣어주고, 윌리암슨수액빨이딱따구리는 단위 시간마다 상 하 좌 우로 한 칸 이동할 수 있으므로 만약 다음에 갈 곳이 범위 안이고, 방문한 적이 없으며 장애물이 아닌 경우에는 이동할 수 있으므로 다음 칸을 방문했다고 표시해주고 큐에 다음 위치 정보를 넣어주었습니다. 만약 다음 위치가 1이 아니고 0이 아닐 경우 즉, 음식이 있는 경우이기 때문에 현재까지의 이동 거리를 ans 변수에 넣어주고 리턴해 주었습니다.

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

예제

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Main_BJ_1062_가르침 {     static int result,N,K;     static boolean [] alphbet;     static String [] words;       public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st ;                  st = new StringTokenizer(br.readLine()," ");                  N = Integer.parseInt(st.nextToken());         K = Integer.parseInt(st.nextToken());                  if(K<5) {             System.out.println(0);             return;         }else if(K==26) {             System.out.println(N);             return;         }                  alphbet = new boolean[26];         alphbet['a'-'a']=true;         alphbet['n'-'a']=true;         alphbet['t'-'a']=true;         alphbet['i'-'a']=true;         alphbet['c'-'a']=true;              words = new String[N];         for(int i=0;i<N;i++) {             String str = br.readLine().replaceAll("anta|tica", "");             words[i] = str;         }                      check(0,0);         System.out.println(result);     }          static void check(int index, int cnt) {         if(cnt==K-5) {             wordCheck();             return;         }                  for(int i=index; i<26;i++) {             if(!alphbet[i]) {                 alphbet[i]= true;                 check(i, cnt+1);                 alphbet[i]=false;             }         }     }          static void wordCheck() {         int count=0;                  for(int i=0;i<N;i++) {             boolean check=true;                          for(int j=0;j<words[i].length();j++) {                 if(!alphbet[words[i].charAt(j)-'a']) {                     check= false;                     break;                 }             }             if(check) count++;         }         result = Math.max(result, count);     }      } Colored by Color Scripter

cs

 

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

예제

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class Main_BJ_2146_다리만들기 {     static int N, min =Integer.MAX_VALUE;     static int [][] map;     static boolean [][] visited;     static int [] dx = {-1,0,1,0};     static int [] dy = {0,1,0,-1};       public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  N = Integer.parseInt(br.readLine());                  map = new int[N][N];         visited = new boolean[N][N];                  for(int i=0;i<N;i++) {             st = new StringTokenizer(br.readLine()," ");             for(int j=0;j<N;j++) {                 map[i][j] =Integer.parseInt(st.nextToken());             }         }                  int count=1;         for(int i=0;i<N;i++) {             for(int j=0;j<N;j++) {                 if(map[i][j]==1 && !visited[i][j]) {                     count++;                      counting(i,j,count);                 }                 }         }                  for(int i=0;i<N;i++) {             for(int j=0;j<N;j++) {                 if(map[i][j]!=0) {                     visited = new boolean[N][N];                     bridge(i,j);                 }             }         }         System.out.println(min);     }          public static void bridge(int x, int y) {         int num = map[x][y];         Queue<int []> queue = new LinkedList<int[]>();         visited[x][y] = true;         queue.offer(new int[] {x,y,0});                  while(!queue.isEmpty()) {             int[] info = queue.poll();                          for(int i=0;i<4;i++) {                 int nx = info[0]+dx[i];                 int ny = info[1]+dy[i];                                  if(range(nx,ny) && !visited[nx][ny]) {                     visited[nx][ny] = true;                     if(map[nx][ny]==0) {                         queue.offer(new int[] {nx,ny, info[2]+1});                     }                     else if(map[nx][ny]!=num) {                         min = Math.min(info[2], min);                         return;                     }                                      }                              }         }     }               public static void counting(int x, int y, int count) {         Queue<int []> queue = new LinkedList<int[]>();         map[x][y] = count;         visited[x][y] = true;         queue.offer(new int[] {x,y});                  while(!queue.isEmpty()) {             int[] info = queue.poll();                          for(int i=0;i<4;i++) {                 int nx = info[0]+dx[i];                 int ny = info[1]+dy[i];                                  if(range(nx,ny) && map[nx][ny]==1 && !visited[nx][ny]) {                     map[nx][ny]=count;                      visited[nx][ny] = true;                     queue.offer(new int[] {nx,ny});                 }             }         }     }          public static boolean range(int x, int y) {         return x>=0 && y>=0 && x<N && y<N;     }   } Colored by Color Scripter

cs

 

풀이 방법

지도가 주어질 때, 가장 짧은 다리를 하나 놓아 두 대륙을 연결할 수 있는 다리의 최소 길이를 구하는 문제였습니다. 먼저 count 변수를 통해 각 대륙들을 구분해 주었습니다. 그리고 한 대륙에서 다른 대륙으로 다리를 놓을 수 있는지 확인하기 위해 bfs() 메소드를 통해 상하좌우로 이동하면서 다른 대륙으로 연결할 수 있는지 확인해주었습니다. 만약 도착한 대륙이 출발한 대륙의 번호와 일치하지 않은 경우에는 두 대륙을 연결할 수 있는 다리를 놓을 수 있으므로 min 변수에 다리 길이를 넣어 리턴해주었습니다. 다리를 연결할 수 있는 모든 경우를 확인해 다리의 최소 길이를 구해주었습니다.

문제

고대 미스테리로 전해지는 여우의 울음소리를 밝혀내기 위해 한신이는 고성능 녹음기로 무장하고 숲으로 들어갔다. 하지만 숲에는 동물들이 가득해, 녹음된 음성에는 다른 동물들의 울음소리가 섞여 있다. 그러나 한신이는 철저한 준비를 해 왔기 때문에 다른 동물들이 어떤 울음소리를 내는지 정확히 알고 있다. 그러므로 그 소리를 모두 걸러내면 남은 잡음은 분명히 여우의 울음소리일 것이다.

입력

첫 번째 줄에는 테스트케이스의 개수 T가 입력된다. 각 테스트케이스는 아래와 같이 구성되어 있다.

테스트케이스의 첫 줄에는 몇 개의 단어로 이루어진 녹음된 소리가 입력된다. 단어는 알파벳 소문자로만 이루어져 있으며 공백으로 구분된다. 단어의 길이는 최대 100글자이고, 단어의 개수는 최대 100개이다. 다음 줄부터는 여우를 제외한 동물들의 울음소리가 <동물> goes <소리>의 형태로 입력된다. 최소 1마리, 최대 100마리이며, 이름은 최대 100글자이고 실제로 존재하는 동물의 이름이다. 여우를 제외한 동물의 울음소리는 한 단어이고 최대 100글자이다.

마지막 줄에는 한신이가 알고 싶어하는 질문이 주어진다. what does the fox say?

출력

각 테스트케이스마다 여우의 울음소리를 한 줄씩, 녹음된 순서대로 출력한다. 여우의 울음소리가 녹음되어 있음이 보장된다. (알려진 것과는 달리, 여우는 모스 부호로 의사소통하지 않는다.)

예제

코드

풀이 방법

여우의 울음소리를 한 줄씩, 녹음된 순서대로 출력하는 문제였습니다. 여우를 제외한 동물들의 울음소리가 <동물> goes <소리>의 형태로 입력되기 때문에 띄어쓰기를 기준으로 단어를 나누었을 때, 세 번째 단어가 the가 아닐 경우에는 list에 넣어둔 울음소리 중 동일한 동물의 소리를 list에서 제거해주었습니다. 만약 세 번째 단어가 the일 경우에는 while문을 빠져나와 남은 울음소리를 차례대로 출력해주었습니다.

문제

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.

마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸린다. 공주님이 있는 곳에 정확히 T시간만에 도달한 경우에도 구출할 수 있다. 용사는 상하좌우로 이동할 수 있다.

성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.

우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.

입력

첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)

두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.

출력

용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.

만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.

예제

코드

풀이 방법

용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있는 최단 시간을 구하는 문제였습니다. 예전에 이 문제와 비슷한 문제를 접해본 적이 있어 3차원 배열을 이용해 빠르게 방향을 잡을 수 있었습니다. 먼저 용사의 위치인 (0,0)을 시간과 함께 큐에 넣어주었습니다. 용사가 상하좌우로 움직이면서 전설의 명검인 그람을 구하면 벽이 있는 칸일지라도, 벽을 부수고 이동할 수 있기 때문에 3차원 배열을 이용해 그람을 가지고 있을 때와 가지고 있지 않을 때를 나눠주었습니다. 만약 그람을 가지고 있을 경우에는 방문하지 않은 곳이라면 어디든지 이동할 수 있으므로 바로 방문처리와 함께 큐에 넣어주고, 그람을 가지고 있지 않은 경우에는 벽이 아닌 길인 곳으로만 이동할 수 있으므로 다음 이동할 곳이 그람인지 길인지를 확인해 큐에 넣어주었습니다. 이 과정을 반복해 만약 용사가 제한시간 T시간 내에 공주님이 있는 (N-1, M-1)에 도착했다면 최단 시간을 출력해주고 아닌 경우에는 Fail를 출력해주었습니다.

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

예제

코드

풀이 방법

두 변을 공유하지 않는 스티커 점수의 최댓값을 구하는 문제였습니다. 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없기 때문에, 스티커 점수의 합을 저장해 줄 dp [][] 배열에 현재 뗄 스티커를 기준으로 다른 줄에 있는 스티커 중 해당 스티커의 왼쪽에 있는 2개의 스티커의 점수를 비교해 더 큰 값을 해당 스티커의 값과 더해줬습니다. 마지막으로 첫 번째 줄의 맨 오른쪽에 있는 값과 두 번째 줄의 맨 오른쪽에 있는 값을 비교해 더 큰 값을 출력해주었습니다.

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

예제

코드

풀이 방법

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하는 문제였습니다. 준규는 위치한 곳에서 오른쪽, 아래, 오른쪽 아래 대각선으로 이동할 수 있으므로, 해당 위치에서 위쪽, 왼쪽, 왼쪽 위 대각선 중에서 가장 큰 값과 해당 위치의 값을 더해주면서 (N, M)에 도착했을 때의 값을 출력해주었습니다.