끼루루룩

1. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2. 설명 문제에 설명되어 있는 조건에 따라 최솟값을 구하고, min 배열에 저장했다. bottom-up 방식 사용 DP에서 가장 어려운게 (내기준) 점화식 규칙을 뽑아내는 건데 이 문제는 문제에서 말해줘서 쉬웠다. 3. 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int[]..

1. 문제 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 2. 설명 비트마스크 다뤄보는 문제. 시간 오버되서 통과못할뻔 했다; 그냥 비트마스크 공부하는 겸 풀어봄 3. 코드 import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(S..

1. 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 2. 설명 오름차순으로 정렬해서 더했다. 3. 코드 import java.util.StringTokenizer; import java.util.Arrays; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] ..

1. 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 설명 Knapsack Problem 알고리즘이라고 유명한 DP 문제이다. 점화식은 아래와 같다. weight[i]j 일 때는 dp[i][j] = dp[i-1][j] 이다. 3. 코드 import java.util.StringTokenizer; import java.io.BufferedReader; import jav..

1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 2. 설명 벽 부수는거 때문에 힘들었던 문제... 방문여부와 큐에 벽(wall)을 추가해서 풀었다. wall은 최대 1까지 될 수 있고, 0일 때만 하나 부술 수 있도록 함. 어렵당 3. 코드 import java.util.Queue; import java.util.StringTokenizer; import java.io.BufferedReader; impo..

1. 문제 https://www.acmicpc.net/problem/1697 2. 설명 늘 풀던 그 BFS 최단거리 방식으로 풀었다. 입력은 두개밖에 없어서 Scanner로 받았다. 3. 코드 import java.util.Queue; import java.util.LinkedList; import java.util.Scanner; public class Main { static void bfs(int n, int k) { Queue q = new LinkedList(); int[] cnt = new int[100001]; q.add(n); while(!q.isEmpty()) { n = q.poll(); // 현재 수빈의 위치 if(n==k) break; if(n+1=0 && cnt[n-1]==0) { ..

1. 문제 https://www.acmicpc.net/problem/7576 2. 설명 BFS 최단경로랑 비슷하게 풀면 된다. 다 익는 최소 날짜를 구하는 거라 조금 다르긴 한데 엇비슷.. 다른 분들은 시간도 메모리도 적게드는데 어떻게 한거지ㅠ 3. 코드 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 { static int[] goX = {-1, 1, 0, 0}; static int[] goY = {0..

1. 문제 https://www.acmicpc.net/problem/2178 2. 설명 BFS - 최단경로 문제 하나씩 방문할 때마다 distance를 더해줬다. 그리고 따로 boolean visited를 선언하지 않고 방문하고 나서는 0으로 바꿔줬다. 3. 코드 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 { static int[] goX = {-1, 1, 0, 0}; static int[] goY..