본문 바로가기

알고리즘 문제풀이 입문: 코딩테스트 대비/섹션 8. DFS, BFS 활용14

바둑이 승차(DFS) 설명철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. 입력첫 번째 줄에 자연수 C(1둘째 줄부터 N마리 바둑이의 무게가 주어진다. 출력첫 번째 줄에 가장 무거운 무게를 출력한다. 예시 입력 1 259 58158423361 예시 출력 1242 문제 해결 철수가 가지고 있는 바둑이들 중에서 무게 C 를 초과하지 않으면서 가장 무거운 무게로 바둑이들을 트럭에 실을 수 있는 무게를 구하는 문제이다. 이는 DFS를 이용해 해결할 수 있다.  public class P.. 2024. 5. 10.
합이 같은 부분집합(DFS : 아마존 인터뷰) 설명N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 입력첫 번째 줄에 자연수 N(1두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다. 출력첫 번째 줄에 “YES" 또는 ”NO"를 출력한다. 예시 입력 1 61 3 5 6 7 10  예.. 2024. 5. 10.
반응형

티스토리툴바