import java.util.*;
/**
테스트 1 〉 통과 (0.02ms, 73.7MB)
테스트 2 〉 통과 (0.02ms, 81.8MB)
테스트 3 〉 통과 (0.02ms, 93MB)
테스트 4 〉 통과 (0.08ms, 73.3MB)
테스트 5 〉 통과 (0.68ms, 97.1MB)
테스트 6 〉 통과 (0.92ms, 78.1MB)
테스트 7 〉 통과 (1.79ms, 88.4MB)
테스트 8 〉 통과 (2.52ms, 77.9MB)
테스트 9 〉 통과 (12.39ms, 86.3MB)
테스트 10 〉 통과 (11.06ms, 133MB)
테스트 11 〉 통과 (12.38ms, 126MB)
테스트 12 〉 통과 (10.15ms, 124MB)
테스트 13 〉 통과 (19.70ms, 122MB)
테스트 14 〉 통과 (14.05ms, 139MB)
테스트 15 〉 통과 (14.80ms, 137MB)
테스트 16 〉 통과 (6.80ms, 140MB)
테스트 17 〉 통과 (8.43ms, 121MB)
테스트 18 〉 통과 (0.01ms, 73.3MB)
테스트 19 〉 통과 (0.02ms, 76.4MB)
테스트 20 〉 통과 (0.02ms, 92.6MB)
테스트 21 〉 통과 (0.02ms, 86.7MB)
테스트 22 〉 통과 (0.02ms, 72.6MB)
테스트 23 〉 통과 (0.02ms, 73.3MB)
테스트 24 〉 통과 (8.87ms, 129MB)
테스트 25 〉 통과 (5.05ms, 122MB)
테스트 26 〉 통과 (6.71ms, 124MB)
테스트 27 〉 통과 (6.67ms, 143MB)
테스트 28 〉 통과 (9.39ms, 124MB)
테스트 29 〉 통과 (9.20ms, 144MB)
테스트 30 〉 통과 (10.53ms, 128MB)
테스트 31 〉 통과 (0.01ms, 85.3MB)
테스트 32 〉 통과 (0.01ms, 69.4MB)
테스트 33 〉 통과 (0.01ms, 79.3MB)
테스트 34 〉 통과 (0.02ms, 73.2MB)
**/
class Solution {
public int[] solution(int[] sequence, int k) {
int length = Integer.MAX_VALUE;
int startIdx = -1, endIdx = -1;
int start = 0, end = 0, sum = 0;
while(end < sequence.length) {
sum += sequence[end++];
while(sum > k && start < end) {
sum -= sequence[start++];
}
if(sum == k && length > end - start) {
length = end - start;
startIdx = start;
endIdx = end-1;
}
}
return new int[]{startIdx, endIdx};
}
}
import java.util.*;
/**
테스트 1 〉 통과 (8.41ms, 89.2MB)
테스트 2 〉 통과 (7.23ms, 86.9MB)
테스트 3 〉 통과 (8.58ms, 92.2MB)
테스트 4 〉 통과 (8.04ms, 86.9MB)
테스트 5 〉 통과 (9.12ms, 84.4MB)
테스트 6 〉 통과 (13.46ms, 76.7MB)
테스트 7 〉 통과 (7.15ms, 87.2MB)
테스트 8 〉 통과 (7.34ms, 81.1MB)
테스트 9 〉 통과 (10.70ms, 90.2MB)
테스트 10 〉 통과 (9.32ms, 84.1MB)
테스트 11 〉 통과 (8.33ms, 81.3MB)
테스트 12 〉 통과 (9.85ms, 72.7MB)
테스트 13 〉 통과 (10.36ms, 79.9MB)
테스트 14 〉 통과 (6.95ms, 79.9MB)
테스트 15 〉 통과 (9.31ms, 75.7MB)
테스트 16 〉 통과 (7.38ms, 81.3MB)
테스트 17 〉 통과 (8.24ms, 83.1MB)
테스트 18 〉 통과 (11.41ms, 90.3MB)
테스트 19 〉 통과 (12.52ms, 76.5MB)
테스트 20 〉 통과 (16.39ms, 92.8MB)
테스트 21 〉 통과 (9.73ms, 85.1MB)
테스트 22 〉 통과 (10.66ms, 72.7MB)
테스트 23 〉 통과 (0.08ms, 72.2MB)
테스트 24 〉 통과 (10.36ms, 94.8MB)
테스트 25 〉 통과 (0.05ms, 86.5MB)
테스트 26 〉 통과 (0.08ms, 84.2MB)
테스트 27 〉 통과 (10.00ms, 83.8MB)
테스트 28 〉 통과 (0.15ms, 73.7MB)
테스트 29 〉 통과 (10.99ms, 85.6MB)
테스트 30 〉 통과 (10.33ms, 73.8MB)
테스트 31 〉 통과 (8.54ms, 91.8MB)
**/
class Solution {
public static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
public char[][] arr = new char[5][5];
public static boolean isInRange(int x, int y) {
return 0 <= x && x< 5 && 0 <= y && y < 5;
}
public List<Integer> solution(String[][] places) {
List<Integer> ans = new ArrayList<>();
testcase : for(int t =0; t< places.length; t++) {
for(int i=0;i<5;i++) {
arr[i] = places[t][i].toCharArray();
}
for(int i=0;i<5;i++) {
for(int j=0;j<5;j++) {
if(arr[i][j] == 'P') {
// 거리 체크
Queue<int[]> check = new ArrayDeque<>();
for(int idx=0;idx<4;idx++) {
int x = i+dx[idx], y = j+dy[idx];
if(isInRange(x, y) && arr[x][y] == 'P') {
System.out.println(x+" "+y);
ans.add(0); continue testcase;
}
else if(isInRange(x, y) && arr[x][y] == 'O') {
check.add(new int[] {x, y, idx});
}
}
while(!check.isEmpty()) {
int[] loc = check.poll();
for(int idx=0;idx<4; idx++) {
if(idx == 0 && loc[2] == 2) {
continue;
}
if(idx == 2 && loc[2] == 0) {
continue;
}
if(idx == 1 && loc[2] == 3) {
continue;
}
if(idx == 3 && loc[2] == 1) {
continue;
}
int x = loc[0]+dx[idx], y = loc[1]+dy[idx];
if(isInRange(x, y) && arr[x][y] == 'P') {
System.out.println(x+" "+y);
ans.add(0); continue testcase;
}
}
}
}
}
}
ans.add(1);
}
return ans;
}
}
import java.io.*;
import java.util.*;
class Main {
static int[] dx = {0, -1, 0}, dy = {1, 0, -1}; // bfs를 위한 델타 배열 생성(위로는 못 올라감)
static int[][] mm, arr;
static int N, M;
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M]; // 유적 금화를 저장하는 배열
mm = new int[N][M]; // 메모이제이션(위치, 방향 저장)
// 유적 내 금화 저장
for(int i=0;i<N;i++) {
st = new StringTokenizer(bf.readLine());
for(int j=0;j<M;j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
boolean[][] visited = new boolean[N][M];
visited[N-1][M-1] = true;
mm[0][0] = arr[0][0];
System.out.println((1000000000+dp(N-1, M-1, visited)));
}
public static int dp(int x, int y, boolean[][] visited) {
// if(mm[x][y] != 0) return mm[x][y];
int returnVal = arr[x][y];
int maxRoute = 0;
// 현 위치 기준 좌, 우, 상 에서 내려오는 경우 중 가장 큰 값 체크
for(int i=0;i<3;i++) {
int nX = x+dx[i];
int nY = y+dy[i];
if(isInRange(nX, nY) && !visited[nX][nY]) {
visited[nX][nY] = true;
maxRoute = Math.max(maxRoute, dp(nX, nY, visited));
visited[nX][nY] = false;
}
}
// if(x == N-1 && y == M-1) {
// for(int i=0;i<N;i++) {
// for(int j=0;j<M;j++) {
// System.out.print(visited[i][j]+" ");
// }
// System.out.println();
// }
// }
return mm[x][y] = returnVal + maxRoute;
}
public static boolean isInRange(int x, int y) {
return 0 <= x && x < N && 0 <= y && y < M;
}
}
일단 저는 메모이제이션을 통해 탑다운 방식으로 풀어보려 했어요.
(N-1, M-1) 에서의 최댓값을 구하려면, (N-2, M-1) 과 (N-1, M-2)에서의 최댓값 중 더 큰 것을 고르면 된다고 생각했습니다.
하지만 여기서 논리적인 오류가 발생하는데..
(0, 0)에서 시작한다.
(N-1, M-1)에서의 최댓값을 가지는 경로가 (a, b)를 지난다고 가정했을 때, (a, b)에서의 최댓값을 가지진 않을 수 있다.
이 두 가지를 고려하지 않았습니다...
예를 들어봅시다.
3 5
1 1 1 3 4
0 0 5 2 -1
0 0 1 1 1
의 input이 있다고 가정합니다.
제 코드로 돌려본다면, 12라는 output이 나오게 됩니다.
하지만 정답은 19 입니다.
네
그냥 설계부터 잘못된 코드입니다!
아무튼 그래서 다른 방법을 찾게되었고,
가장 첫 행에서는 왼쪽에서 오른쪽으로밖에 이동할 수 없다.
라는 점을 깨달았습니다.
// 가장 첫 행 계산하기 -> 우측으로밖에 가지 못함
mm[0][0] = arr[0][0];
for(int i=1;i<M;i++) {
mm[0][i] = mm[0][i-1] + arr[0][i];
}
그래서 mm 배열 중 가장 첫 행은, 직전 값에 해당 칸의 value를 더한 값으로 업데이트 해줬습니다.
다음 행부터는 가짓수가 증가합니다.
왼쪽에서 오른쪽으로 이동하거나
오른쪽에서 왼쪽으로 이동하거나
위에서 아래로 이동한다.
이 세 가지입니다.
위에서 아래로 순차적으로 내려올 수 있기 때문에,
두 번째 행부터 차근차근 계산을 해줄겁니다.
각 행마다 fromLeft (왼쪽에서 오른쪽), fromRight (오른쪽에서 왼쪽) 배열을 만들어줍니다.
fromLeft의 가장 왼쪽 값과, fromRight에서 가장 오른쪽 값은, 위에서밖에 내려와 업데이트 되지 못합니다.
