완전탐색 (34) 썸네일형 리스트형 [백준 / BOJ] 1052 물병 문제 출처 : www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 지민이는 N개의 물병을 갖고있다. 각 물병에는 물을 무한대로 부을 수 있는데, 처음에 모든 물병에는 물이 1리터씩있다. 지민이는 N개의 물병을 적절히 합쳐 K개이하의 물병으로 만들려하는데, 물병을 합칠때 는 다음 규칙에 따라 합칠수있다. - 같은 물이 들어있는 물병만 합칠수있다. 이때, 물병을 더 이상 합칠수없다면, 1리터의 물이 들어있는 물병을 추가할수있다. K개 이하의 물병을 만들기위해 추가해야할 .. [백준 / BOJ] 1035 조각 움직이기 문제 출처 : www.acmicpc.net/problem/1035 1035번: 조각 움직이기 최대 5개의 조각이 있는 5*5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 5*5크기의 보드에 최대 5개의 조각이있다. 이 조각을 적절히 움직여서 모든 조각이 연결되도록 할려고한다. 조각은 상하좌우 한칸으로 이동시킬수 있다고할때, 모든 조각을 연결하는 최소한의 이동 횟수를 구하는 문제다. 풀이 처음에는(1년전??) BFS로 풀려했는데, BFS는 항상 최단경로를 보장하므로 하나의 조각을 기준으로 잡고 나머지 조각을 해당 조각으로 이동하는 횟수를 BFS로 구해주는로직을짰.. [백준 / BOJ] 17144 미세먼지 안녕! 문제 출처 : www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구사과는 미세먼지를 제거하기위해 공기청정기를 설치하려고한다. 공기 청정기는 항상 1번 열에 설치되어있고, 크기는 두행을 차지한다. 공기청정기가 없는 칸에는 미세먼지가 있다. 미세먼지는 매초 마다 확산을 하는데, 확산되는 양은 다음과같다. 확산되는 양 : Ay,x / 5 y,x에 남는양 : Ay,x - (Ay,x/5 * 확산된 방향의 개수) 미세먼지가 확산을 한 이후에는 공기청정기가 작동하여 미세.. [백준 / BOJ] 1941 소문난 칠공주 문제 출처 : www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 5*5그리드에 학생들의 파가 주어진다. (이다솜파 : S, 임도연파 : Y) 이다솜은 자신의 파를 늘리기위해 소문난 칠공주를 결성하기로했다. 칠공주가 되기위해선 3가지 조건이 필요한데, 1. 칠공주에 속하는 학생들은 서로 인접해있어야한다. 2. 7명의 학생으로 구성되어야한다. 3. 이다솜파보다 임도연파가 더 많아야한다. 이때, 소문난 칠공주를 결성하는 모든 경우의수를 구하는 문제다. 풀이 푸는데 2일.. [백준 / BOJ] 15970 화살표 그리기 문제 출처 : www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 점들의 색깔과 위치(x좌표)가 주어진다. 각각의 점을 가까우면서 같은색깔인 점에 연결할려할때, 연결한 선의 최대거리를 구하는 문제다. 풀이 N이 크지않아 완전탐색으로도 풀리는문제다. 문제를 잘 읽지않고 점들의 색깔이 항상 2개인줄 알고풀다가 몇번 틀렸었다. 1. 점들을 입력받을때, 같은 색깔은 같은 벡터에 들어가도록 입력받는다. 2. 각 벡터를 N번 정렬한다. 3. 현재 점의 idx에서 .. [백준 / BOJ] 20157 화살을 쏘자 문제 출처 : www.acmicpc.net/problem/20157 20157번: 화살을 쏘자! 호준이는 요즘 활 쏘기에 푹 빠져 있다. 열심히 활 쏘기를 연습하던 호준이는 쏠 때 마다 10점이 나오는 경지에 이르렀다. 이렇다 보니 한 방향으로 있는 과녁에 쏘는 것에 실증을 느낀 호준이는 www.acmicpc.net 풍선들의 (X,Y)가 주어졌을때, 호준이가 화살을 쏠때, (화살은 포물선이 아닌 직선으로 날라감) 한번에 터트릴수 있는 풍선의 최대갯수를 구하는 문제다. 풀이 풍선의 갯수가 10만개이다. 일반적인?? 완전탐색으로 모든경우를 볼경우 O(N^2)이 나와서 시간초과가 뜬다. 완전탐색으로 풀되, 저장을 다르게 해야하는데, 나는 딕셔너리에 {기울기, 해당 기울기의 풍선의 갯수} 로 저장해 주는식으로 .. [백준 / 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방향으로 할수있으며, (대각선 + 상하좌우) 상근이는 항상 가장 많은사람과 악수를 할수있는 자리에 앉는다고 할때, 미사가 진행되는동안 몇번악수를 할수있는지 구하는 문제다. 풀이 범위가 크지않아서 완전탐색으로 풀리는 문제였다. 주의할점이 "상근이가 악수를 하는 경우" 가 아니라 "모든 사람이 악수를 하는 경우.. 이전 1 2 3 4 5 다음