stonesy

해결방법수를 순서대로 순회하면서 투 포인터로 서로 다른 두 수의 합으로 나타낼 수 있는 수의 개수를 구한다. ⇒ O(N^2) (N≤2000)*수의 위치가 다르면 값이 같아도 다른 수이다. 코드import java.util.*;import java.io.*;// O(N^2)public class Main_1253_G4_좋다_투포인터 { static int N; static int[] numbers; public static void main(String[] args) throws IOException{ // 1. 입력 및 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

해결방법2개의 용액을 골라야한다. 일반적으로 조합을 구하기 위해서는 O(2^N)의 시간복잡도를 가진다. 위 문제의 경우 2≤N≤100000이므로 적용불가능하다. (대략 N이 10을 넘어가면 불가능)투포인터로 접근한다.left+right의 절댓값이 answer보다 작다면 answer 갱신(left와 right 위치 저장)left와 right의 용액을 더했을 때 양수이면 → right-1left와 right의 용액을 더했을 때 음수이면 → left+1left결론적으로 투포인터로 O(N)의 시간복잡도로 문제를 해결할 수 있다.  코드import java.util.*;import java.io.*;// 308ms, 투포인터, O(N)public class Main_2467_G5_용액_투포인터 { stati..

해결방법최단 경로이므로 BFS로 접근한다.단, 이동하는 도중에 한개의 벽을 부수고 이동할 수 있다는 변수가 있다. 벽의 위치를 저장하고 먼저 벽을 부수고 출발하면 최악의 경우 시간복잡도가 O((N*M)^2)로 시간초과가 발생한다.따라서 3차원 배열로 거리/방문체크를 해야한다. 3차원 배열인 이유는 map 자체가 2차원 배열이고 벽을 부수지 않은 경우/벽을 부순경우를 나눠야 한다. 벽을 부수고 간 것이 먼저 도착하는 경우 벽을 부수지 않고 도착한 것이 방문처리되어 통과되지 못할 수 있기 때문이다. 코드1(거리 비교)import java.util.*;import java.io.*;public class Main_2206_G3_벽부수고이동하기_거리체크 { static int N,M; // N(1 ≤ N ..

해결방법기둥을 정렬한 후 가장 높은 기둥을 알아낸다.왼쪽 ~ 가장 높은 기둥까지 면적을 더한다. 왼쪽에서 가장 높은 기둥을 기준으로 가장 높은 기둥이 갱신될 때마다 면적을 더한다.오른쪽 ~ 가장 높은 기둥까지 위와 같은 로직을 반복한다.⇒ 정렬에 O(Nlog), 면적을 더하는데 O(N)의 시간복잡도가 소요된다. 코드import java.util.*;import java.io.*;// 112mspublic class Main_2304_S2_창고다각형 { static int N; static Tower[] tower; static class Tower{ int w, h; public Tower(int w, int h){ this.w=w; ..