[코딩테스트] [2529] 부등호 & [9095] 1,2,3 더하기 & [12101] 1,2,3 더하기 2

[2529] 부등호

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

256 MB

31504

18633

12677

58.215%

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다.

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다.

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다.

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.

문제풀이

이 문제는 부등호 기호 '<' 와 '>'를 k개 만큼 입력받아 부등호 관계를 만족하는 정수 중에 최대값과 최소값을 구하는 문제이다.

필요한 변수 선언

javastatic boolean[] visited = new boolean[10]; *// 0-9 사용 여부*
static char[] operators; *// 입력된 부등호 배열*
static List<String> results = new ArrayList<>(); *// 유효한 숫자 저장*

1. 입력 처리: 부등호 개수(k)와 부등호 문자열을 공백 제거 후 배열로 변환
2. DFS 탐색: 0-9 숫자를 순차적으로 조합하며 부등호 조건 검사
3. 결과 출력: results 리스트의 첫 번째(최소)와 마지막(최대) 값 출력

Base Case (종료 조건)

javaif (depth == k + 1) {
    results.add(num);
    return;
}

• depth: 현재 선택한 숫자 개수
• k+1 자리 숫자가 완성되면 결과 저장
• 예시: k=3일 때 4자리 숫자 완성 시 종료

Recursive Case (탐색 로직)

javafor(int i = 0; i <= 9; i++) {
    if (visited[i]) continue; *// 이미 사용된 숫자 건너뛰기*
    
    if (depth == 0 || Check(prev, i, operator)) {
        visited[i] = true;
        Dfs(num + i, depth + 1); *// 다음 숫자 선택*
        visited[i] = false; *// 백트래킹*
    }
}

• 0-9 순차 탐색: 작은 숫자부터 시도 → 자연스러운 사전식 순서 생성
• Check() 조건:
  • 첫 번째 숫자 선택(depth=0) 시 조건 없음
  • 이후 선택 시 operators[depth-1] 부등호 조건 만족 확인

조건 검증 함수

javastatic boolean Check(int a, int b, char operator) {
    return (operator == '<') ? a < b : a > b;
}

• 동작 예시:
  • operator='<' → 이전 숫자(a) < 현재 숫자(b)
  • operator='>' → 이전 숫자(a) > 현재 숫자(b)

사전식 순서 생성 메커니즘

단계 탐색 순서 결과 예시 (k=2, 부등호: < >)

1단계	0 → 1 → 2 → ... → 9	첫 유효 시퀀스: "010" (불가) → "012" (유효)
2단계	0 → 1 → 2 → ... → 9	마지막 유효 시퀀스: "987" → "989"

• 최소값: results.get(0)
• → DFS가 0부터 시작해 가장 먼저 발견한 유효 조합
• 최대값: results.get(last)
• → 9부터 시작하는 큰 숫자들이 나중에 발견됨

전체코드

import java.io.*;
import java.util.*;

class Main {
    static int k;
    static boolean[] visited = new boolean[10];
    static char[] operators = new char[10];
    static List<String> results = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        operators = br.readLine().replace(" ", "").toCharArray();
        
        Dfs("", 0);
        
        System.out.println(results.get(results.size() - 1));
        System.out.println(results.get(0));        
    }
                           
    static void Dfs(String num, int depth) {
        if (depth == k + 1) {
            results.add(num);
            return;
        }
        
        for(int i = 0; i <= 9; i++) {
            if (visited[i]) continue;
            
            if (depth == 0 || Check(num.charAt(depth - 1) - '0', i, operators[depth - 1])) {
                visited[i] = true;
                Dfs(num + i, depth + 1);
                visited[i] = false;
            }
        }
    }
    
    static boolean Check(int a, int b, char operator) {
        if (operator == '<') return a < b;
        else return a > b;
    }
}

[9095] 1, 2, 3 더하기

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초 (추가 시간 없음)

512 MB

139949

92835

64668

64.919%

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

문제풀이

이 문제는 정수 n을 1, 2, 3의 합으로 구하는 방법이 총 몇가지인지 구하는 문제이다.

재귀 함수 조건

• 종료 조건 (Base Case)
  • sum > goal: 합이 목표값을 초과하면 0 반환
  • sum == goal: 합이 목표값과 일치하면 1 반환 (유효한 경우)
• 재귀 호출
  • 현재 합에 1, 2, 3을 각각 더한 세 가지 경우를 탐색
  • 모든 경우의 수를 합산하여 반환

재귀 트리 구조

text0
├─ 1 (sum=1)
│  ├─ 2 (sum=3) → 유효 (1)
│  ├─ 3 (sum=4) → 무효 (0)
│  └─ 4 (sum=5) → 무효 (0)
├─ 2 (sum=2)
│  ├─ 3 (sum=5) → 무효 (0)
│  ├─ 4 (sum=6) → 무효 (0)
│  └─ 5 (sum=7) → 무효 (0)
└─ 3 (sum=3) → 유효 (1)

전체코드

시간 복잡도

• 최대 깊이: goal (예: n=10 → 10단계)
• 각 단계 분기: 3개 → O(3ⁿ)
• 효율성: n=10 → 약 59,049회 연산

import java.util.*;
import java.io.*;

class Main {
    static int T;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        while (T-->0) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(solve(0, n));
        }
    }

    static int solve(int sum, int n) {
        if (sum > n) return 0;
        if (sum == n) return 1;

        return solve(sum + 1, n) + solve(sum + 2, n) + solve(sum + 3, n);
    }
}

[12101] 1, 2, 3 더하기 2

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초 (추가 시간 없음)

512 MB

4497

2830

2304

63.037%

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

이를 사전순으로 정렬하면 다음과 같이 된다.

1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 1+3
5. 2+1+1
6. 2+2
7. 3+1

정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 231-1보다 작거나 같은 자연수이다.

출력

n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.

문제풀이

이 문제는 정수 n을 1, 2, 3의 합으로 나타내는 방법들을 구하고 사전순으로 정렬하여 K번째 방법을 출력하는 문제이다.

필요한 변수 선언 및 초기화

결과를 저장할 result 배열을 선언해주고 n과 k를 입력받는다.

    static List<String> result = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        <--생략-->

Base Case

• 현재 조합을 문자열로 변환하여 저장한다.
• 자동으로 사전순서로 정렬이 된다.

        if (sum == target) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < current.size(); i++) {
                if (i > 0) sb.append("+");
                sb.append(current.get(i));
            }
            result.add(sb.toString());
            return;
        }

• 만약 값이 목표값보다 초과한다면 종료한다.

if (sum > target) return;

Recursive Case

• 1 → 2 → 3 순서로 숫자를 선택 (사전순 보장)
• 선택한 숫자를 current 리스트에 추가
• 재귀 호출로 다음 단계 진행
• 백트래킹으로 마지막 숫자 제거 (다른 경로 탐색

    for (int num = 1; num <= 3; num++) {
        current.add(num); // 숫자 선택
        generateCombinations(target, current, sum + num); // 재귀 호출
        current.remove(current.size() - 1); // 백트래킹 (선택 취소)
    }

재귀함수 호출 및 결과 출력

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        dfs(n, new ArrayList<>(), 0);
        
        if (k > result.size()) {
            System.out.println(-1);
        } else {
            System.out.println(result.get(k-1));
        }
    }

전체코드

import java.util.*;

class Main {
    static List<String> result = new ArrayList<>();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        solve(0, new ArrayList<>(), n);
        
        if ( k > result.size() ) {
            System.out.println(-1);
        } else {
            System.out.println(result.get(k - 1));
        }
    }
    
    static void solve(int sum, List<Integer> current, int target) {
        if ( sum == target) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < current.size(); i++) {
                if ( i > 0 ) sb.append("+");
                sb.append(current.get(i));
            }
            result.add(sb.toString());
            return;
        }
        
        if ( sum > target ) return;
        
        for (int num = 1; num <= 3; num++) {
            current.add(num);
            solve(sum + num, current, target);
            current.remove(current.size() - 1);
        }
    }
    
}