팡세영
Log sey
팡세영
전체 방문자
오늘
어제
  • 분류 전체보기 (73)
    • PS (45)
      • programmers (13)
      • 백준 (29)
    • Android (16)
    • Daily (0)
    • Kotlin (6)
    • Design Pattern (1)
    • Java (1)
    • Flutter (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • BFS
  • Android
  • 백준
  • 자바
  • binding
  • 구현
  • 실버
  • TestCode
  • 해쉬맵
  • programmers
  • 이분탐색
  • DFS
  • 정렬
  • LEVEL2
  • ArcitecturePattern
  • 프로그래머스
  • 완전탐색
  • 하단네비게이션바
  • CustomView
  • java
  • mvvm
  • 문자열
  • 의존성 주입
  • 안드로이드
  • programmers #프로그래머스
  • Kotlin
  • 코틀린
  • flutter
  • compose
  • 골드

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
팡세영

Log sey

백준 - 캠프 준비 16938
PS/백준

백준 - 캠프 준비 16938

2023. 3. 1. 17:21


https://www.acmicpc.net/problem/16938

 

16938번: 캠프 준비

난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다.

www.acmicpc.net


  • 조합 백트래킹으로 완전 탐색

 

[Java] 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main
{

    static int ans = 0;
    static int arr[];
    static boolean visited[];
    static int l,r,x;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input[] = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        l = Integer.parseInt(input[1]);
        r = Integer.parseInt(input[2]);
        x = Integer.parseInt(input[3]);

        arr = new int[n];
        visited = new boolean[n];

        input = br.readLine().split(" ");
        for(int i=0; i<n; i++) arr[i] = Integer.parseInt(input[i]);

        for(int i=2; i<=n; i++) combination(0, i);

        System.out.println(ans);
    }

    public static void combination(int start, int select){
        if(select == 0){

            int sum = 0;
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;

            for(int i=0; i<arr.length; i++){
                if(visited[i]){
                    sum += arr[i];
                    min = Math.min(min, arr[i]);
                    max = Math.max(max, arr[i]);
                }
            }

            if(sum >= l && sum <= r && max - min >= x) ans ++;

            return;
        }

        for(int i=start; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                combination(i + 1, select - 1);
                visited[i] = false;
            }
        }
    }


}

'PS > 백준' 카테고리의 다른 글

백준 - 연속합 1912 java  (0) 2023.03.06
백준 - 문자열 집합 조합하기 25328  (0) 2023.03.03
[백준] - 도영이가 만든 맛있는 음식 2691  (0) 2023.02.28
[백준] - Australian Voting (호주식 투표법) 4419  (0) 2023.02.13
[백준] - 피보나치함수 (1003)  (0) 2022.11.24
    'PS/백준' 카테고리의 다른 글
    • 백준 - 연속합 1912 java
    • 백준 - 문자열 집합 조합하기 25328
    • [백준] - 도영이가 만든 맛있는 음식 2691
    • [백준] - Australian Voting (호주식 투표법) 4419
    팡세영
    팡세영
    Android, CS, PS

    티스토리툴바