Solve001
문제번호: 11047(동전 0)
풀이
- 동전을 오름차순으로 입력하기 때문에 따로 정렬할 필요는 없다
- 가장 큰 동전부터 탐색을 하며 K보다 작을 시에 해당 동전이 K원을 만들 수 있는 가장 큰 동전이다.
- 입력 K원이 0원이 될때까지 빼주며 K보다 작은 동전이 발견될 시에 계속 cnt를 1씩 증가시킨다.
import java.util.Scanner;
class Main {
public static void main(String[] args){
Scanner stdin = new Scanner(System.in);
int n = stdin.nextInt();
int k = stdin.nextInt();
int cnt = 0;
int[] coin = new int[n];
for(int i = 0; i < n; i++){
coin[i] = stdin.nextInt();
}
for(int j = n - 1; j >= 0; j--){
while(true){
if(k >= coin[j]){
k -= coin[j];
cnt++;
}
else
break;
}
}
System.out.print(cnt);
}
}
문제번호: 1914(하노이 탑)
풀이(시간초과)
- 재귀를 이용하여 풀이 N-1개의 원판을 첫번째에서 중간 기둥으로 옮긴다
- 첫번째 기둥 맨아래 원판은 세번째 기둥으로 옮긴다.
- 재귀를 이용하여 중간 기둥으로 옮겼던 N-1개의 원판을 세번째 기둥으로 옮긴다.
- 재귀
- 원판이 2개일 시, 위에서 한개를 하나의 그룹으로 본다.
- 원판이 3개일 시, 위에서 두개를 하나의 그룹으로 보면 위에서 두개를 옮기는 방법을 이용
- 원판이 4개일 시, 위에서 세개를 하나의 그룹으로 보면 위에서 세개를 옮기는 방법을 이용
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class boj_1914 {
static int cnt = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
hanoi(N, 1, 3);
System.out.println(cnt);
if(N <= 20) {
hanoi_print(N, 1, 3);
}
}
static void hanoi(int n, int x, int y){
if(n > 1){
hanoi(n-1, x, 6 - x - y);
}
cnt += 1;
if(n > 1){
hanoi(n-1, 6 - x - y, y);
}
}
static void hanoi_print(int n, int x, int y){
if(n > 1){
hanoi_print(n-1, x, 6 - x - y);
}
System.out.printf("%d %d\n",x, y);
if(n > 1){
hanoi_print(n-1, 6 - x - y, y);
}
}
}
- cnt = 2^N - 1인데 N을 100까지 표현하려면 시간초과가 뜬다.
- BigInteger를 이용해서 cnt 값을 출력한다.
풀이수정
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
BigInteger cnt = new BigInteger("2");
cnt = cnt.pow(N);
cnt = cnt.subtract(BigInteger.ONE);
System.out.println(cnt);
if(N <= 20) {
hanoi_print(N, 1, 3);
}
}
static void hanoi_print(int n, int x, int y){
if(n > 1){
hanoi_print(n-1, x, 6 - x - y);
}
System.out.println(x + " " + y);
if(n > 1){
hanoi_print(n-1, 6 - x - y, y);
}
}
}
문제번호: 1449(수리공 항승)
풀이
- 구멍의 개수와 테이프의 길이를 입력한다.
- 처음에 구멍의 개수에 맞게 테이프 칠을 하도록 cnt를 올린다.
- 그 다음 테이프의 길이와 구멍 사이의 길이를 체크
- 구멍을 먼저 오름차순으로 정렬
Arrays.sort()
- 그 다음 가장 첫 구멍을 값에 저장한 다음, 뒤에 있는 값들과 비교
뒤 구멍 - 앞 구멍 + 1
이 테이프의 길이보다 짧으면 cnt 1을 빼준다. (테이프 하나로 막을 수 있으므로)- 그 다음 뒤에있는 구멍과도 비교를 해서 그 길이가 테이프 길이보다 크다면 index를 해당 구멍부터 시작하도록 옮겨준다.
- 구멍을 먼저 오름차순으로 정렬
import java.util.Arrays;
import java.util.Scanner;
import static java.lang.Math.abs;
public class boj_1449{
public static Scanner stdin = new Scanner(System.in);
static int cnt;
public static void main(String[] args){
int n = stdin.nextInt();
int l = stdin.nextInt();
int[] hole = new int[n];
for(int i = 0; i < n; i++){
hole[i] = stdin.nextInt();
}
System.out.println(solution(hole, l));
}
static int solution(int[] hole, int l) {
Arrays.sort(hole);
int a = hole[0];
cnt = hole.length;
for(int i = 1; i < hole.length; i++){
if((abs(a - hole[i]) + 1 <= l)){
cnt--;
}
else {
a = hole[i];
}
}
return cnt;
}
}
문제번호: 1080(행렬)
풀이
- 3x3의 행렬을 한꺼번에 뒤집기 때문에 만약 크기가 6x6인 행렬이라면 index 0 ~ 3 을 확인하고 4부터는 확인할 필요가 없다.
- 따라서
index 0 ~ index N - 3
까지만 확인을 해주면 된다. index 0 ~ index N - 3
에서 행렬a와 행렬b의 값이 다르면 해당 인덱스로부터 3x3 만큼 reverse 한다.- reverse 과정이 끝난 후에 행렬a와 행렬b가 동일한지 확인을 해야한다.
- 6x6에서 index 0 ~ 3까지 확인하고 reverse를 수행한 후에, index 4와 index 5가 행렬끼리 서로 다르다면 이 연산으로는 같은 행렬이 될 수 없음을 의미한다.
public class Main {
static int n;
static int m;
static int cnt = 0;
static int[][] a;
static int[][] b;
public static void main(String[] args) {
Scanner stdin = new Scanner(System.in);
n = stdin.nextInt();
m = stdin.nextInt();
a = new int[n][m];
b = new int[n][m];
for (int i = 0; i < n; i++) {
String str = stdin.next();
for (int j = 0; j < m; j++) {
a[i][j] = str.charAt(j) - '0';
}
}
for (int i = 0; i < n; i++) {
String str = stdin.next();
for (int j = 0; j < m; j++) {
b[i][j] = str.charAt(j) - '0';
}
}
System.out.println(solution());
}
static void reverse(int x, int y) {
for (int i = x; i < x + 3; i++) {
for (int j = y; j < y + 3; j++) {
if (a[i][j] == 1) {
a[i][j] = 0;
}
else {
a[i][j] = 1;
}
}
}
}
static int solution(){
for (int i = 0; i < n - 2; i++) {
for (int j = 0; j < m - 2; j++) {
if (a[i][j] != b[i][j]) {
reverse(i, j);
cnt++;
}
}
}
for (int i = 0 ; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] != b[i][j]) {
return -1;
}
}
}
return cnt;
}
}
문제번호: 1174(줄어드는 숫자)
Arraylist, collection 공부하기
풀이
- 최고로 큰 줄어드는 숫자인 987654321은
2^N-1번째
이므로 index 1024부터는 -1을 출력 - 987654321은
int
타입으로는 표현할 수 없기 때문에long
타입 사용
- 0 ~ 9 는 줄어드는 숫자이므로 0 ~ 9로 시작하며 재귀를 이용한다
- 만약
solution(5, 1, list)
가 실행된다면 list에 5, 50, 51, 510, 52, 520, 521, 5210, 53, 530, 531, 5310, 532, 5320, 5321, 53210 ...... 이 재귀적으로 계속 추가된다- 일의자리 수보다 작은 숫자들이 뒤로 계속 붙게됨
- 자릿수가 10자리가 되면
list
를 리턴한다 - 현재
list
에 존재하는 요소들은 정렬되지 않는 상태이므로 정렬시킨다. - 0이 제일 가장 작은 첫번째 줄어드는 숫자이므로 0번 index에 0이 저장되어 있으므로 1번 인덱스부터 출력되게 한다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
ArrayList<Integer> list = new ArrayList<>();
for(int num = 0; num < 10; num++) {
solution(num, 1, list);
}
Collections.sort(list);
if(T > 1023){
System.out.println(-1);
}
else {
System.out.println(list.get(T - 1));
}
}
static ArrayList solution(long num, int digit, ArrayList list){
if(digit > 10){
return list;
}
list.add(num);
for(int i = 0; i < 10; i++){
if(num % 10 > i){
solution(num * 10 + i, digit + 1, list);
}
}
return list;
}
}
문제번호: 1105(팔)
풀이
- 자리수가 커지면 무조건 0이 된다.
- 자리수가 커질때 생기는 100, 1000, 10000
은 8이 없으므로
- 자리수가 커질때 생기는 100, 1000, 10000
- 두개의 수를 큰자리수부터 비교하며 같은지 확인한다.
- 자리수의 숫자가 모두 다르거나 8이 없으면 8이 없어도 되므로 그냥 0이다.
- 해당 자리수의 숫자가 다르면 중단한다.
- 예를들어 819와 830라고 할때, 1과 3은 다르므로 자리수가 바뀔때
(820)
8이 존재하지 않을 수 있다.
- 예를들어 819와 830라고 할때, 1과 3은 다르므로 자리수가 바뀔때
- 해당 자리수의 숫자가 같으면 그 숫자가 8인지 확인하고 8이면 cnt 하나 올린다.
- 예를들어 820과 835라고 할때, 앞자리 8은 바뀔 수 없고 2, 3은
830
이 나올 수 있으므로 stop
- 예를들어 820과 835라고 할때, 앞자리 8은 바뀔 수 없고 2, 3은
public class Main {
static int cnt = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
String x = st.nextToken();
String y = st.nextToken();
System.out.println(solution(x, y));
}
static int solution(String x, String y){
if(x.length() == y.length()) {
for (int i = 0; i < x.length(); i++) {
if(x.charAt(i) == y.charAt(i)){
if(x.charAt(i) == '8'){
cnt++;
}
}
else
break;
}
}
return cnt;
}
}
문제번호: 1092(배)
풀이
- 배가 옮길 수 있는 무게, 박스의 무게를 역순으로 정렬한다.
- 가장 큰 박스를 가장 큰 배에 못 실으면 -1 반환
- 가장 큰 박스부터 가장 큰 배부터 싣는다.
- 박스 idx, 배 idx 두 가지를 이용한다.
- 만약 박스의 무게가 배보다 크면 박스 idx를 하나씩 늘려가면서 실을 수 있는지 확인
- 배에 모두 실으면 cnt를 1올리고 다시 idx들을 초기화하고 실행
- box에 요소가 다 없어지면 cnt 반환
public class Main {
static ArrayList<Integer> box = new ArrayList<Integer>();
static ArrayList<Integer> ship = new ArrayList<Integer>();
static int cnt = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int shipcnt = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < shipcnt; i++) {
ship.add(Integer.parseInt(st.nextToken()));
}
int boxcnt = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < boxcnt; i++) {
box.add(Integer.parseInt(st.nextToken()));
}
System.out.println(solution(shipcnt));
}
static int solution(int s) {
Collections.sort(box);
Collections.sort(ship);
Collections.reverse(box);
Collections.reverse(ship);
if (box.get(0) > ship.get(0)) {
return -1;
}
while (!box.isEmpty()) {
int ship_idx = 0;
int box_idx = 0;
while (ship_idx < s) {
if (ship.get(ship_idx) >= box.get(box_idx)) {
box.remove(box_idx);
ship_idx++;
}
else if (ship.get(ship_idx) < box.get(box_idx)) {
box_idx++;
}
if(box_idx == box.size()){
break;
}
}
cnt++;
}
return cnt;
}
}
문제번호: 1946(신입사원)
풀이
- 시간 복잡도를 줄이기 위해 서류심사 성적을 오름차순으로 정렬을 한다.
- (정렬 하는법 제대로 공부하기)
- 서류심사의 성적이 정렬이 된 상태이기 때문에 2등 부터는 1등의 면접심사 등수보다 높아야 한다.
- 최소값 변수를 하나 선언하고 1등의 면접심사 등수를 대입한다.(기준값)
- 2등부터 면접심사 등수를 체크한다
- 만약 최소값에 저장되어 있는 면접심사 등수보다 높다면 최솟값을 해당 등수 면접심사 등수로 바꾼다.
- 뒤에 있는 등수 사람들은 서류심사 등수가 낮기때문에 면접은 무조건 높아야 한다. 따라서 최소값보다 항상 커야함.
- 만약 최소값에 저장되어 있는 면접심사 등수보다 낮다면 해당 인원은 채용되지 않기 때문에 전체 인원에서 1감소
- 만약 최소값에 저장되어 있는 면접심사 등수보다 높다면 최솟값을 해당 등수 면접심사 등수로 바꾼다.
public class Main {
static ArrayList<point> arr;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
public static void main(String[] args) throws IOException {
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
int n = Integer.parseInt(br.readLine());
arr = new ArrayList<point>();
for (int j = 0; j < n; j++) {
st = new StringTokenizer(br.readLine(), " ");
arr.add(new point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
System.out.println(solution(n));
}
}
static int solution(int n){
Collections.sort(arr, new Comparator<point>() {
@Override
public int compare(point o1, point o2) {
return o1.x > o2.x ? 1 : -1;
}
});
int cnt = arr.size();
int min = arr.get(0).y;
for(int i = 1; i < n; i++){
if(min < arr.get(i).y){
cnt--;
}
else
min = arr.get(i).y;
}
return cnt;
}
}
class point{
int x;
int y;
public point(int x, int y){
this.x = x;
this.y = y;
}
}
문제번호: 1263(시간관리)
풀이
- 일단 가장 우선적으로 처리해야 할일부터 정렬한다.
- 정렬 후에 임의의 i번 idx에서 끝내는 시간이 x_time이라면 0 ~ i까지의 인덱스들의 걸리는 시간의 합이 x_time을 넘어서는 안된다.
- 넘는다면 애초에 해당 idx일은 할 수가 없는 일.
- 가장 처음 해야할일의 걸리는 시간이 y_time 이라면 y_time까지 반복문을 돌려준다.
- 여기서 2의 조건에 위배되는 사항이 있으면 -1을 반환한다.
- 그렇지 않다면 해당 반복문의 idx가 답이된다.
- 중첩 반복문 나올때 flag를 이용하자.
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static ArrayList<Time> arr = new ArrayList<Time>();
static int time = 0;
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine(), " ");
arr.add(new Time(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
System.out.println(solution(n));
}
static int solution(int n){
Collections.sort(arr, new Comparator<Time>() {
@Override
public int compare(Time o1, Time o2) {
return o1.si > o2.si ? 1 : -1;
}
});
boolean flag = false;
for(int i = 0; i <= arr.get(0).si; i++){
int idx = 0;
int sum = i;
while(idx < n) {
sum += arr.get(idx).ti;
if (sum > arr.get(idx).si){
if(i == 0){
return -1;
}
flag = true;
break;
}
idx++;
}
if(flag == true){
break;
}
time = i;
}
return time;
}
}
class Time{
int ti;
int si;
public Time(int ti, int si){
this.ti = ti;
this.si = si;
}
}
문제번호: 1068(트리)
풀이
- DFS, BFS 공부
- DFS 풀때 배열 선언 예시.
ArrayList<Integer>[] tree = new ArrayList[개수];
- 입력 받은 개수만큼 ArrayList 선언하고, 각각에 인덱스마다 인접노드를 저장한다.
- 양방향 입력
- tree[i].add(parent); - tree[parent].add(i);
- 재귀를 이용하여 DFS 방식으로 트리를 순회하며, 삭제 노드를 순회할 때 재귀 stop.
- 마지막 leaf를 순회하게 되면 count 하나씩 증가시킨다.
- 실수 한 부분: index[0]이 무조건 root가 되는게 아님.
public class boj_1068 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static ArrayList<Integer>[] tree;
static boolean[] isvisited;
static int leaf_cnt = 0;
static int root = 0;
static int delete_idx = 0;
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
isvisited = new boolean[n];
tree = new ArrayList[n];
for(int i = 0; i < n; i++) {
tree[i] = new ArrayList<Integer>();
isvisited[i] = false;
}
st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < n; i++){
int parent = Integer.parseInt(st.nextToken());
if(parent != -1) {
tree[i].add(parent);
tree[parent].add(i);
}
else root = i;
}
delete_idx = Integer.parseInt(br.readLine());
if(delete_idx == root){
System.out.println(0);
}
else{
DFS(root);
System.out.println(leaf_cnt);
}
}
static void DFS(int node){
isvisited[node] = true;
boolean haschild = false;
for(int i = 0; i < tree[node].size(); i++){
if(tree[node].get(i) != delete_idx && !isvisited[tree[node].get(i)]) {
haschild = true;
DFS(tree[node].get(i));
}
}
if(!haschild){
leaf_cnt++;
}
}
}
Author And Source
이 문제에 관하여(Solve001), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sksk713/Solve001저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)