끼루루룩

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://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 2. 설명 탐욕법관련된 문제다. 첫번째 배열로 정렬하고, 차량 진출지점을 기준으로 카메라 위치를 선정해 나갔다. 겹쳐지지 않는 부분이면 카메라를 한대 추가하고, 그 차량의 진출지점에 다시 카메라를 설치했다. 기본적으로 한 대 이상의 카메라가 설치되어야 되기 때문에 answer의 기본값을 1로 잡고 시작했다. 3. 코드 import java.util.*; class Solution { public int solution(int[][] routes) { 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://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같�� programmers.co.kr 2. 설명 우선순위 큐를 사용해서 풀었다! 처음에 리스트 사용해서 정렬하는 방식으로 풀었는데 효율성 이전에 정확성에서 틀려버리더라 왜그런지는 모르겠다. 3. 코드 import java.util.PriorityQueue; class Solution { public int solution(int[] scoville, int K) { int..

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://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 2. 설명 number의 첫번째 인덱스로부터 인덱스 + k 까지 최댓값을 찾아서 answer에 삽입하는 방식으로 풀었다. 반복을 진행하는 것은 number 길이 - k 까지만 진행하면 된다. j의 시작을 idx로 잡은 이유는 이미 선택한 최댓값을 지나치기 위해서! 탐욕법은 아직 어렵다. 3. 코드 class Solution { public String solution(String number, int k) { StringBuilder answer = new StringBuilder(); int idx = 0; char max; ..

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..