동환아 공부해야지

문제: https://www.acmicpc.net/problem/2412 조건TimeLimit = 2s(0,0)에서 정상까지 등반할 때, 최소 이동 횟수는 얼마인가? 정상까지 이동할 수 없다면 -1을 출력(x,y)와 (a,b)에 대해 다음 조건을 만족하면 이동할 수 있다|a-x| |b-y| 암벽의 홈 개수는 최대 5만개 풀이완전탐색n이 최대 5만이므로 O(5만)으로 탐색 가능-> 격자 map의 한 변의 크기가 5만인게 아니라, 전체 탐색 가능한 좌표가 5만개임을 유의이동은 8방향으로, 길이가 1, 2인 상황을 모두 탐색해야한다-> 여기서 3차원 for문이 사용됨-> 1: 방향, 2: x좌표 이동거리, 3: y좌표 이동거리-> 따라서 8*2*2 = 32 x, y좌표 범위가 너무 크기 때문에, 방문 체크에..

문제: https://www.acmicpc.net/problem/7576 조건TimeLimit = 1s하루 뒤에, 익은 토마토의 상하좌우 안익은 토마토가 익는다토마토가 모두 익는 최소 일수를 구하라. 단, 모두 익지 못하면 -1을 출력하라M,N은 1000이하, 1은 익은 토마토, 0은 익지 않은 토마토, -1은 빈공간이다 풀이완전탐색 -> 최소 시간/거리를 구해야하므로 BFS 사용상하좌우를 탐색하는 BFS의 시간복잡도는 O(4*V^2) ~= O(V^2)이므로, 최대 O(100만)으로 해결 가능 코드import java.io.*;import java.util.*;public class Main { static int n; static int m; static int[][] map; static List r..

문제: https://www.acmicpc.net/problem/3967 조건TimeLimit = 2s1크기가 1 이상의 부분수열 중, 합이 S가 되어야 함 풀이완전탐색최대 12개의 순열을 나열해야한다. O(12!)이므로 약 4억이라 불가능..하지만 가지치기를 잘 해보면 가능할지도? (1억과 크게 차이가 안나니까)순열이므로 visited를 통해 중복 관리를 해주자12개의 숫자를 모두 다 사용했을 때를 trigger로 한다이때 모든 라인에 대해, 각 라인의 합이 26이어야한다필요한 숫자들을 new int[12] 배열로 가정했을 때, 각 라인에 해당하는 index는 다음과 같다line 1 -> 0, 2, 5, 7line 2 -> 1, 2, 3, 4line 3 -> 0, 3, 6, 10line 4 ->..

문제: https://www.acmicpc.net/problem/16938 조건TimeLimit = 2s문제수 (1=100만), 난이도 (A문제를 고를 수 있는 모든 경우의 수를 구하여라 풀이완전탐색 -> 백트래킹문제를 특정 개수만큼 뽑으라는게 아니기 때문에 선택/미선택 방식으로 가자N이 15라면, O(2^15) ~= O(6천만) 이므로 가능 (2^26 이하면 다 가능)이때 순서가 필요없으므로 조합이다 (visited 필요없음)선택한 문제는 boolean[]으로 기억해두고, sum할때 사용하자문제들은 난이도 순서대로 정렬시켜서 가장 쉬운문제와 가장 어려운 문제를 뽑을 수 있게 하자 코드import java.io.*;import java.util.*;public class Main { static Str..

문제: https://www.acmicpc.net/problem/13913 조건TimeLimit = 2s수빈이 위치(0수빈이가 1초마다 이동한다 -> 걷기 = x+=1, 순간이동 = 2x (x = 현재위치)수빈이가 동생을 찾는 가장 빠른 시간과, 그때의 이동 순서를 출력하라 풀이최단시간이므로 BFS를 사용하자N이 10만으로 크지만, 1차원 배열이므로 완전탐색이 가능하다이동 순서는 매번 배열을 들고다닐 필요가 없고, 직전에 어디서 왔는지만 기억하면 된다따라서 이동순서는 int[]로 기억해두자 코드import java.io.*;import java.util.*;public class Main { static StringBuilder sb; static StringTokenizer st; static int..

문제: https://www.acmicpc.net/problem/2589 조건TimeLimit = 1s상하좌우 이동만 가능하고, 한 칸 이동하는데 한 시간 소요됨육지(L), 바다(W)중에 육지로만 이동 가능두 지점을 이동하는데 걸리는 최단 시간중, 최댓값은? 풀이BFS최단시간을 구해야하므로 BFS를 사용한다이때 최단시간들중 최댓값을 구하는 것이므로, 매번 최대시간을 초기화해주자출발점은 모든 'L'로 전체를 탐색한다참고로 BFS의 TimeLimit은 다음처럼 구한다상하좌우로 움직일 수 있으므로, 시작점부터 전체를 탐색하는 경우 간선 E = 4*n*m이다이때 모든 지점을 탐색한다면, 전체 순회는 모든 Node의 수와 같으므로 V = n*m이다따라서 BFS의 전체 탐색은 O(4*(n*m)*(n*m)) ~= O..

문제: https://www.acmicpc.net/problem/1753 조건TimeLimit = 1s방향 그래프정점(1시작점이 주어질 때, 1번부터 V번까지 시작점으로부터의 최단거리를 출력하라 풀이다익스트라우선순위 큐를 사용한다면 시간복잡도는 O((V+E)logV)이므로-> 대략 O(30만 * log30만) 이므로 충분히 가능핵심 변수는 대략.. Node = class {idx, w}, graph = List[Node], dist = int[] 정도PriorityQueue의 poll과 offer를 적절히 사용하자 코드import java.io.*;import java.util.*;public class Main { static StringTokenizer st; static StringBuilder ..

문제: https://www.acmicpc.net/problem/15666 조건TimeLimit = 2sN개중 M개를 고른 수열 (1수열 내에서 중복이 가능하지만, 수열은 비내림 차순이어야 한다가능한 수열들을 사전순으로 출력하라 풀이완전탐색N과 M이 모두 8이라면 -> 8*8*8*...*8 = 8^8 = 대략 1600만. 따라서 완전탐색 가능중복 가능하므로 visited 필요없음대신 이전에 고른 수보다 커야하므로, 이전에 고른 수의 index를 들고다니자이때 기존 배열을 정렬해줘야지 비내림차순이 가능하다또한 한번 골랐던 '수'(index 아님)를 또 고르지 않기 위해, 한번 골랐던 수를 기억해두자 코드import java.io.*;import java.util.*;public class Main { s..

문제: https://www.acmicpc.net/problem/15665 조건TimeLimit = 1sN개중 M개를 고른 수열 (1수열 내에서는 중복 가능하지만, 수열 자체는 중복되면 안됨가능한 모든 수열을 오름차순으로 출력하라 풀이백트래킹전체 수열만 중복 안되면 되므로, 지역변수 pre를 사용해주자 코드import java.io.*;import java.util.*;public class Main { static StringTokenizer st; static StringBuilder sb = new StringBuilder(); static int n; static int m; static int[] arr; static int[] cur; public static void main(String..

문제: https://www.acmicpc.net/problem/11725 조건TimeLimit = 1s노드 수 (2트리의 루트는 1이다각 node의 부모를, 2번부터 n번까지 순서대로 출력하여라 풀이n이 10만이지만, BFS를 사용하면 depth 한번만 돌면 된다. 따라서 O(10만)으로 가능양방향으로 연결1부터 BFS를 시작parent = new int[n+1]로 부모를 저장해두자 코드import java.io.*;import java.util.*;public class Main { static StringTokenizer st; static int n; static List[] edge; static int[] parent; static boolean[] visited; public static..