기록방

👉 문제링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 정수 N을 1로 만드는 가장 적은 연산 수를 출력한다. 연산은 -1, /3, /2 세 가지가 있다. DP, DFS, BFS 모두 풀이 가능하다. 🔸 DP 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { // Input BufferedReader br = new BufferedReader..

👉 문제링크 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 🔸 문제 분석 🔸 int 범위의 값을 넣는 'I' 연산과 최대값 혹은 최소값을 빼는 'D'연산이 k번 수행된다. 최종 연산 후 결과를 출력한다. k의 최대값이 1,000,000 이므로 값을 저장할 자료구조를 힙 형태로 구현해야 한다. 힙정렬이 적용된, 우선순위 큐(Priority Queue) 혹은 TreeMap을 사용한다. 🔸 Priority Queue 🔸 import java.io.BufferedReader; import java.io.IOEx..

👉 문제링크 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 🔸 문제 분석 🔸 T번의 테스트 케이스에서 다음 계산을 반복한다. 연산 p를 입력받는다. n 크기의 배열을 입력받는다. 연산을 수행한다. R : 뒤집기 D : 첫 번째 수 버리기 n과 p의 길이의 최대값이 10만이므로 R연산마다 배열을 직접 뒤집으면 시간초과가 난다. 배열의 시작과 끝 인덱스에 각각 포인터를 두고, 뒤집힌 상태를 보며 D연산을 수행한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.Input..

👉 문제링크 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 🔸 문제 분석 🔸 T번의 테스트 케이스를 돌린다. 계산기는 10진수 4자리 숫자로 0000~9999까지 처리할 수 있다. 4가지 연산 D, S, L, R이 있다. A부터 시작해 B가 되는 최소길이 명령어를 출력한다. 가중치가 없는 최단거리(최소경로) 문제이므로 BFS 를 사용한다. 큐에서 현재 숫자와 지금까지의 연산을 기록할 클래스를 만든다. D : 2n%10000 S : n-1 (n=1이면, 9999) L : (LShift) n = n..

👉 문제링크 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 🔸 문제 분석 🔸 N x M 연구소 격자 맵에 빈 칸은 0, 벽은 1, 바이러스는 2로 입력된다. 바이러스는 상하좌우 인접한 빈 칸으로 퍼져나간다. 벽을 3개 세워서 바이러스가 다 퍼진 후 나올 수 있는 빈 칸의 수 최대값을 출력한다. 3개의 벽을 설치할 위치를 조합으로 구한다. BFS로 바이러스가 퍼진 상태로 만든다. 0의 수를 세서 최대값을 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOExcept..