stonesy

해결 방법먼저, 전체 문자열에서 폭발 문자열을 찾고 다시 문자열을 이어붙여 탐색하는 풀이가 떠오른다. 최악의 경우 전체 문자열의 길이가 N, 폭발 문자열의 길이가 1d일때, N*(N-1)(N-2)…*1의 연산이 필요하다. 즉, O(N^2)이 되어 시간초과가 발생할 것이다. 그래서 스택을 사용해서 O(N)으로 문제를 해결해야 한다. 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri..

해결 방법완전 탐색으로 접근하면 시간 초과가 발생한다. 한 지점에서 3방향으로 이동할 수 있고, 지점이 NM개 있으므로 O(3^(NM))의 시간복잡도가 소요되기 때문이다.첫 번째 행의 경우 오직 왼 → 오 방향만 가능하므로 따로 계산해주고 두 번째 행부터는 왼 → 오 / 오 → 왼을 비교해주어야 한다. 즉, 이전 단계의 최적 결과를 바탕으로 다음 단계에서의 최적 결과를 구해야하므로 DP로 접근한다고 볼 수 있다. 따라서 O(N*M)의 시간복잡도로 해결할 수 있다. 코드import java.util.*;import java.io.*;public class Main { static int MIN_VAL = -987654321; static int N,M; // (1≤N, M≤1,000) st..