Nirsa

문제 링크 : https://www.acmicpc.net/problem/1145

[백준] 1145번: 적어도 대부분의 배수 (브론즈1, 브루트포스 알고리즘, JAVA)

해당 문제는 입력받은 5개의 숫자 중, 3개 이상이 공통적으로 가지는 배수를 찾아내는 브루트포스(완전탐색) 문제 입니다. 우선 사용자로부터 입력받은 후 오름차순으로 정렬하고 최솟값을 가지는 0번 인덱스에서 부터 무한루프를 사용하여 탐색을 시작합니다.

public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	
    	String input = br.readLine();
    	sb.append(input);
    	
    	String[] strArr = sb.toString().split(" ");
        
    	int value = 1;
        
        while(true) {
        	// 로직 작성
    	}
    }
}

아래 코드는 while문 안의 로직인데, 우선 배수가 몇개인지 찾을 count 변수를 항상 0으로 초기화 합니다. 이후 입력받은 strArr 배열의 0번인덱스부터 마지막 인덱스(4) 까지 반복하여 0으로 나누어 떨어지는 수가 있다면 count의 값을 증가시킵니다.

만약 count의 값이 3 이상일 경우  break로 while문을 빠져나온 후 count된 value를 출력하고, 3 미만일 경우 value의 값을 1씩 증가시키며 또 다시 strArr 배열의 모든 값을 확인하며 0으로 나누어 떨어지는 수의 개수를 구하게 됩니다.

while(true) {
    int count = 0;

    for(int i=1; i<strArr.length; i++) {  // 배열을 한바퀴 돌음
        if(value % Integer.parseInt(strArr[i]) == 0) { // min으로 나눈 값이 0(배수)라면
            count++;
        }
    }

    if(count >= 3) { // 배수가 3개 이상일 경우 출력 후 break
        break;
    } else {
    	value++;
    }
}
System.out.println(value);

문제 링크 : https://www.acmicpc.net/problem/1253

[백준] 1253번: 좋다 (골드4, JAVA)

우선 아래의 코드를 사용하여 사용자로부터 입력을 받고 배열로 변환 합니다. 단, 문제를 풀 때 수월하게 풀기 위해서 따로 원본 배열과 사본 배열을 생성하고 사본 배열을 오름차순 정렬하였습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

int N = Integer.parseInt(br.readLine());

String input = br.readLine();
sb.append(input);

// 스트링 배열로 변환
String[] strArr = sb.toString().split(" ");

// 원본 배열 생성
int[] originA = new int[strArr.length];

// 사본 배열 생성
int[] A = new int[strArr.length];

// 스트링 배열 -> int 배열 변환
for(int i=0; i<A.length; i++) {
    originA[i] = Integer.parseInt(strArr[i]);
    A[i] = Integer.parseInt(strArr[i]);
}

// 사본 배열 오름차순 정렬
Arrays.sort(A);

우선 for 안에 while을 사용하여 볼건데, 로직을 작성하기 전의 코드를 보면 아래와 같습니다. 원본 배열은 어떤 수(현재 인덱스)를 가지고 있어야 하고, 투포인터를 사용해야하기 때문에 오름차순으로 정렬한 배열은 시작 인덱스와 끝 인덱스를 만들어 줍니다.

int answer = 0; // 반환 값
for(int i=0; i<A.length; i++) {
    int number = i; // 어떤 수의 인덱스 (원본 배열) 
    int start = 0;  // 시작 인덱스 (사본 배열)
    int end = A.length-1; // 끝 인덱스 (사본 배열)
    int count = 0; // 중복값 카운트
    
    // 로직 작성
}

문제를 보면 아래와 같은 조건이 있는데, 즉 같은 값을 가지고 있더라도 위치(인덱스)가 다르면 다른 수라고 합니다. 위 코드의 count 배열은 어떤 수(원본 배열)와 시작 또는 끝 인덱스에 위치한 값(사본 배열)이 일치하는게 있다면 1, 없다면 0으로 사용할 예정입니다.

• 애초에  사본 배열에 있는 값을 가지고 비교할 예정이기 때문에 중복되는 값이 있더라도 인덱스의 위치 상관 없이 단 한번만 무시하면 됩니다.
• ex) 원본 배열 : 0 1 4 5 3 4 의 경우 사본 배열로 만들어 오름차순하게 되면 0 1 3 4 4 5 로 됩니다. 이러한 경우일 때 원본 배열의 어느 인덱스에 있던간에 사본 배열의 3번 또는 4번 인덱스에 위치한 값 한번만 무시하면 됩니다. 

위의 코드에서 로직이 한번 더 추가된 코드입니다. 조건식은 다음과 같습니다.

1. 사본 배열의 시작 인덱스 값 = 어떤 수(원본 배열)이 같거나 count가 0이면 true
   → count가 1이라면 이미 중복된 코드를 처리했기 때문에 pass
   → 다음 인덱스의 값을 비교하기 위해 start 값 증가
2. 사본 배열의 끝 인덱스 값 = 어떤 수(원본 배열)이 같거나 count가 0이면 true
   → 다음 인덱스의 값을 비교하기 위해 end 값 감소
3. 그 외의 경우(값이 같지 않고, 중복된 로직이 없었다면) true 

int answer = 0; // 반환 값
for(int i=0; i<A.length; i++) {
    int number = i; // 어떤 수의 인덱스 (원본 배열) 
    int start = 0;  // 시작 인덱스 (사본 배열)
    int end = A.length-1; // 끝 인덱스 (사본 배열)
    int count = 0; // 중복값 카운트
    
    // 추가된 로직
    while(start < end) { // 시작이 종료보다 작을 때
        if(A[start] == originA[number] && count == 0) {
            count++;
            start++;
        } else if(A[end] == originA[number] && count == 0) {
            count++;
            end--;
        } else {
            // 투포인터 로직 작성
            
        }
    }
}

투포인터 로직까지 작성하면 아래와 같습니다. 사본 배열의 시작 인덱스 + 끝 인덱스가 어떤 수(원본 배열)보다 크다면 끝 인덱스를 줄이고, 반대의 경우라면 시작 인덱스를 줄여가며 비교합니다. 만약 시작 인덱스 + 끝 인덱스의 합이 어떤 수(원본 배열)와 같다면 반환값을 증가하고 이미 좋은 수로 판단이 되었기 때문에 추가적인 검사 없이 break로 while을 탈출합니다.

while문이 종료되며 for문이 다시 반복되고, 원본 배열의 다음 인덱스를 비교해가며 좋은 수를 찾아가게 됩니다.

int answer = 0; // 반환 값
for(int i=0; i<A.length; i++) {
    int number = i; // 어떤 수의 인덱스 (원본 배열) 
    int start = 0;  // 시작 인덱스 (사본 배열)
    int end = A.length-1; // 끝 인덱스 (사본 배열)
    int count = 0; // 중복값 카운트
    
    // 추가된 로직
    while(start < end) { // 시작이 종료보다 작을 때
        if(A[start] == originA[number] && count == 0) {
            count++;
            start++;
        } else if(A[end] == originA[number] && count == 0) {
            count++;
            end--;
        } else {
            // 투포인터 로직 작성
            if(A[start]+A[end] > originA[number]) { // 어떤수가 합보다 작을 때
                end--;
            } else if(A[start]+A[end] < originA[number]) { // 어떤수가 합보다 클 때
                start++;
            } else if(A[start]+A[end] == originA[number]) { // 어떤수가 합과 같을 때
                answer++;
                break;
            }
        }
        System.out.println(answer);
    }
}

문제 링크 : https://www.acmicpc.net/problem/11399

11399번: ATM (실버4, JAVA)

사용자가 입력한 값을 String 배열로 받고  int 배열로 변환 후, 필요한 시간의 최솟값을 구해야하기 때문에  오름차순으로 정렬합니다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		sc.nextLine();
		String[] str = sc.nextLine().split(" ");

		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(str[i]);
		}
		
		Arrays.sort(arr);
		
		Main main = new Main();
		main.dfs(arr, 0, 1);
	}

이후 각각 값을 저장할 sum, 반복문을 실행할 index의 값을 늘려가며 반복합니다. 이렇게 한다면 입력값이 [3, 1, 4, 3, 2] 였을 때 위의 코드에서 오름차순으로 정렬한 후 [1, 2, 3, 3, 4] 아래의 반복문에서 1, 1+2, 1+2+3, 1+2+3+3, 1+2+3+3+4를 반복한 후 모든 값을 더한 후 출력하면 구하고자 하는 32의 값이 나오며, return을 사용하여 재귀호출을 중지 합니다.

	void dfs(int[] arr, int sum, int index) {
		for(int i=0; i<index; i++) {
			sum += arr[i];
		}
		if(arr.length == index) {
			System.out.println(sum);
			return;
		}
		dfs(arr, sum, ++index);
	}
}

문제 링크(2839) : https://www.acmicpc.net/problem/2839

문제 링크(10162) : https://www.acmicpc.net/problem/10162

[백준] 2839번: 설탕 배달 (실버4, JAVA)

봉지의 최수 개수(divide)를 선언하고 사용자의 입력(N)을 받은 후 dfs 메소드를 호출합니다.

public class Main {
	int divide;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Main main = new Main();
		
		main.dfs(N);
	}

문제에서 주어진 내용에서 중요한 부분은 `최대한 적은 봉지를 들고 가려고 한다.` 입니다. 최대한 적은 봉지를 들고가기 위해서는 N의 배수일 경우 먼저 계산을 하고, 그 외 (N 나누기의 몫이 0이 아닐 때)를 계산하게 되면 최대한 적은 봉지를 구할 수 있습니다.

아래 코드에서는 최대한 적은 봉지를 구하기 위해서는 5의 배수를 먼저 구하고, 그다음은 3의 배수, 그다음은 5로 나눠 질 때, 마지막으로 3으로 나눠질 때를 구하면 최대한 적은 봉지를 구하게 됩니다. 모두 계산을 해도 N이 0이 아니라면  정확하게 N킬로그램을 만들 수 없기 때문에 -1을 반환 합니다.

    void dfs(int N) {
        if(N%5 == 0 && N != 0) { // N이 5의 배수면 5 빼기
            divide++;
            dfs(N-5);
        } else if(N%3 == 0 && N != 0) { // N이 3의 배수면 3 빼기
            divide++;
            dfs(N-3);
        } else if(N/5 > 0 && N != 0) {
            divide++;
            dfs(N-5);
        } else if(N/3 > 0 && N != 0) {
            divide++;
            dfs(N-3);
        } else if(N == 0) {
            System.out.println(divide);
        } else {
            System.out.println(-1);
        }
    }
}

[백준] 10162번: 전자레인지(브론즈3, JAVA)

해당 문제도 위의 설탕 배달 문제와 동일한 로직으로 풀 수 있습니다. 각각 해당하는 변수들을 생성해주고 사용자의 입력을 받은 후 dfs 메소드를 호출 합니다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	int A = 300;  // 5분
	int buttonA;
	int B = 60; // 1분
	int buttonB;
	int C = 10; // 10초
	int buttonC;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		Main main = new Main();
		main.dfs(T);
	}

dfs 메소드는 해당하는 값을 받아 큰 값부터 나누고, 나누어 진다면 버튼의 클릭 횟수를 증가시킨 후 재귀호출합니다. 단, 재귀호출 시 T의 값을 줄여가다가 0이 된다면 각 버튼들의 클릭 횟수를 출력하고, 0이 아니라면 -1을 출력합니다.

	void dfs(int T) {
		if(T/A != 0) {
			buttonA++;
			dfs(T-A);
		} else if(T/B != 0) {
			buttonB++;
			dfs(T-B);
		} else if(T/C != 0) {
			buttonC++;
			dfs(T-C);
		} else if(T == 0) {
			System.out.printf("%d %d %d", buttonA, buttonB, buttonC);
		} else {
			System.out.println(-1);
		}
	}
}