알고리즘 (2020 : 08 : 10 ~ )/완전탐색 (25) 썸네일형 리스트형 [백준 / BOJ] 9881 Ski Course Design (Java) 문제 출처 : https://www.acmicpc.net/problem/9881 9881번: Ski Course Design Farmer John has N hills on his farm (1 [백준 / BOJ] 9874 Wormholes (Java) 문제 출처 : https://www.acmicpc.net/problem/9874 9874번: Wormholes Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2 [백준 / BOJ] 1092 배 (Java) 문제 출처 : https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 크래인의 갯수 N, 화물박스의 갯수 M이 주어진다. (1 [백준 / BOJ] 1719 택배 문제 출처 : www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net n개의 집하장에 택배가있다. 각 집하장에서 다른 집하장으로 이동거리를 최소화하여 택배를 보낼려한다. m개의 집하장 경로와 이동거리가 주어졌을때, 경로표를 만드는 문제다. (경로표는 현재 집하장에서 다른집하장으로 택배를 이동시킬려할때 가장 먼저 거쳐가야할 집하장을 표시한 표이다.) 풀이 플로이드 와샬을 이용해 푸는문제다. dp배열을 pair로 선언해 로 저장해놓는다. 현재 i,j에 저장된 값보.. [백준 / BOJ] 15970 화살표 그리기 문제 출처 : www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 점들의 색깔과 위치(x좌표)가 주어진다. 각각의 점을 가까우면서 같은색깔인 점에 연결할려할때, 연결한 선의 최대거리를 구하는 문제다. 풀이 N이 크지않아 완전탐색으로도 풀리는문제다. 문제를 잘 읽지않고 점들의 색깔이 항상 2개인줄 알고풀다가 몇번 틀렸었다. 1. 점들을 입력받을때, 같은 색깔은 같은 벡터에 들어가도록 입력받는다. 2. 각 벡터를 N번 정렬한다. 3. 현재 점의 idx에서 .. [백준 / BOJ] 17911 Keyboards in Concert 문제 출처 : www.acmicpc.net/problem/17911 17911번: Keyboards in Concert The first line of input is two space separated integers; n (1 ≤ n ≤ 1 000) the number of instruments, and m (1 ≤ m ≤ 1 000), the number of notes in the tune. This is followed by n lines, each starting with an integer ki (1 ≤ ki ≤ 1 000), the nu www.acmicpc.net 올라브는 전자키보드를 갖고있다. 이 전자키보드로 노래를 연주하려고 하는데, 키보드가 고장나서 모든 음을 연주할수없다. 한번에 .. [백준 / BOJ] 9518 로마 카톨릭 미사 문제 출처 : www.acmicpc.net/problem/9518 9518번: 로마 카톨릭 미사 로마 카톨릭 미사에서 가장 멋진 부분은 사람들이 서로 악수를 하면서 "평화가 함께하기를" 이라고 말하는 평화 의식이다. 성당에는 R개의 벤치가 한 행에 하나씩 있고, 각 벤치에는 총 S명이 앉 www.acmicpc.net 상근이가 교회 미사동안 최대한 많은사람과 악수를 하려고 한다. 악수는 자기 자리에서 8방향으로 할수있으며, (대각선 + 상하좌우) 상근이는 항상 가장 많은사람과 악수를 할수있는 자리에 앉는다고 할때, 미사가 진행되는동안 몇번악수를 할수있는지 구하는 문제다. 풀이 범위가 크지않아서 완전탐색으로 풀리는 문제였다. 주의할점이 "상근이가 악수를 하는 경우" 가 아니라 "모든 사람이 악수를 하는 경우.. [백준 / BOJ] 19942 다이어트 문제 출처 : www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 식재료 N개중 몇개를 선택해서 이들의 영양분(단백질 탄수화물 지방 비타민)이 일정이상이 되어야한다. 각 식재료에는 가격이있다. 이때, 가격을 최소로하는 식재료 조합을 찾는 문제였다. 풀이 완전탐색으로 풀은 문제다. 탐색마다 영양소를 선택하는 경우, 선택하지 않는경우로 총 2가지 선택지가 있으므로, 최대 반복횟수는 2^15가 된다. 풀이는 간단한데, 단백질 탄수화물 지방 비타민 이 있을때, 각각의.. 이전 1 2 3 4 다음