zoaseo
To Infinity And Beyond
zoaseo
전체 방문자
오늘
어제
  • 분류 전체보기 (763)
    • 개발이 좋아서 (381)
      • SAP가 좋아서 (3)
      • Java가 좋아서 (42)
      • Spring이 좋아서 (50)
      • JPA가 좋아서 (0)
      • QueryDSL이 좋아서 (26)
      • Docker가 좋아서 (7)
      • Redis가 좋아서 (7)
      • AWS가 좋아서 (5)
      • CI/CD가 좋아서 (6)
      • Troubleshooting이 좋아서 (4)
      • Kotlin이 좋아서 (7)
      • SQL이 좋아서 (6)
      • HTTP가 좋아서 (21)
      • JavaScript가 좋아서 (30)
      • TypeScript가 좋아서 (6)
      • Vue가 좋아서 (21)
      • Flutter가 좋아서 (61)
      • React가 좋아서 (20)
      • Redux(React)가 좋아서 (2)
      • Angular가 좋아서 (22)
      • HTML이 좋아서 (9)
      • CSS가 좋아서 (15)
      • PHP가 좋아서 (9)
      • Illustrator가 좋아서 (2)
    • 노력이 좋아서 (169)
    • 결과물이 좋아서 (14)
    • 코딩연습이 좋아서 (168)
      • 이론이 좋아서 (62)
      • SQL이 좋아서 (90)
    • 유용한 사이트가 좋아서 (28)
    • Github (2)

인기 글

티스토리

hELLO · Designed By 정상우.
zoaseo

To Infinity And Beyond

코딩연습이 좋아서/이론이 좋아서

DFS, BFS 활용 - 바둑이 승차(DFS)

2024. 12. 13. 22:15

설명

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.

철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.

N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.

둘째 줄부터 N마리 바둑이의 무게가 주어진다.

출력

첫 번째 줄에 가장 무거운 무게를 출력한다.

예시 입력 1 

259 5
81
58
42
33
61

예시 출력 1

242

 

import java.util.Scanner;

public class Main {

    static int c;
    static int n;
    static int max = 0;

    public static void DFS(int L, int sum, int[] a) {
        if(sum > c) return;
        if (L == n) {
            if (sum > max) max = sum;
        } else {
            DFS(L + 1, sum + a[L], a);
            DFS(L + 1, sum, a);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        c = sc.nextInt();
        n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        DFS(0, 0, a);
        System.out.println(max);
    }
}

'코딩연습이 좋아서 > 이론이 좋아서' 카테고리의 다른 글

DFS, BFS 활용 - 중복순열 구하기(DFS)  (0) 2024.12.13
DFS, BFS 활용 - 최대점수 구하기(DFS)  (0) 2024.12.13
DFS, BFS 활용 - 합이 같은 부분집합(DFS : 아마존 인터뷰)  (0) 2024.12.13
Recursive, Tree, Graph(DFS, BFS 기초) - 그래프 최단거리(BFS)  (0) 2024.12.13
Recursive, Tree, Graph(DFS, BFS 기초) - 경로탐색(인접리스트, ArrayList)  (0) 2024.12.13

    티스토리툴바