브루트포스

📖 문제 https://www.acmicpc.net/problem/3019   💡  풀이 방식• 구현, 브루트포스 1. 블록 모양에 따라 올라와야 하는 바닥면의 높이를 저장한다.2. 바닥면에 대해 블록을 끝까지 내릴 수 있는지 반복문으로 검사한다. ⇒ 각 번호에 맞는 빈 공간 수를 뺐을 때 모두 같은 값이 나오면 놓을 수 있는 자리이다!! (참고)    🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152import java.util.*;import java.io.*; public class Main {    static int C,P;    static int[] map; ..

📖 문제 https://www.acmicpc.net/problem/15683  💡  풀이 방식• 시뮬레이션 + 백트래킹 + 브루트포스  각 CCTV의 타입을 받아, 각 타입에 맞춰 회전된 상태를 조합해 사각지대의 최소값을 구한다.CCTV 타입이 1( → )인 경우 : 북(0 / ↑), 남(1 / ↓), 서(2 / ←), 동(3 / →)CCTV 타입이 2( ↔ )인 경우 : 서동(23 / ↔), 북남(01 / ↕ )CCTV 타입이 3(↑→)인 경우 : 북동(03 / ↑→) , 남동(13 / ↓→) , 남서(12 / ↓←) , 북서(02 / ←↑)CCTV 타입이 4( ←↑→ )인 경우 : 북서동(023), 북남동(013), 남서동(123), 북남서 (012)CCTV 타입이 5(↕↔)인 경우 : 북남서동(..

📖 문제 https://www.acmicpc.net/problem/16937   💡  풀이 방식• 브루트포스1. 입력되는 정보들을 저장한다.2. 모든 스티커들에서 2개를 붙이는 경우를 탐색해 최대 넓이를 구한다.  - [스티커1 붙이기] 항상 (0,0)을 기준으로 붙인다. (목적: 다음 스티커를 붙일 수 있는 최대 칸을 남기기 위해)3. 최대 넓이를 구하면 결과로 출력하고, 못 구하면 0을 결과로 출력한다.   🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384..

📖 문제   18428번: 감시 피하기NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복www.acmicpc.net   💡  풀이 방식• 조합(DFS) + BFS 1. 격자를 입력받으면서 학생 S의 위치, 선생님 T의 위치, 빈 칸 X의 위치를 각 리스트에 저장해둔다.이러면 나중에 완전탐색으로 학생, 선생님, 장애물 위치를 따로 안 찾아도 된다.for(int i = 0 ; i   2. 빈 칸 X의 위치들 중 3개를 뽑고, 해당 위치에 장애물을 심었을 때 모든 학생들이 감시를 피할 수 있는지 BFS로 탐색한다.private static void dfs(int..

📖 문제 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 💡 풀이 방식 • BFS + 브루트포스 "모든 최단 거리 중 가장 긴 구간" 모든 육지(L)에서 BFS를 수행하며, 현재 육지에서 다른 위치까지의 가장 긴 시간이 걸리는 거리를 구한다. 그리고 그 거리를 정답과 비교해 더 큰 값으로 정답을 갱신한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 4..

📖 문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💡 풀이 방식 • DFS + BFS + 브루트포스 1. 입력을 받으면서 빈 칸의 위치와 바이러스의 위치를 리스트에 저장해둔다. - 빈 칸 위치 저장한 이유 : 빈 칸 위치들 중 3개만 뽑으려고 할 때 완전탐색으로 모든 빈 칸 위치 안 찾으려고 - 바이러스 위치 저장한 이유 : 완전탐색으로 바이러스 위치 안 찾으려고 2. 빈 칸 중 3개를 뽑아 벽을 세우고, 바이러스를 퍼뜨린다. 2-1) 빈 칸 중 3개 뽑는 방법 : DFS private static void dfs(..

📖 문제 28215번: 대피소 $2$차원 평면의 KOI 마을에 $N$개의 집이 있다. 각 $i$번째 집의 위치는 $(X_i , Y_i)$이다. $i$번째 집과 $j$번째 집 사이의 거리는 $|X_i - X_j | + |Y_i - Y_j |$이다. 즉, 두 집 사이의 거리는 $X$의 차이와 $Y$의 www.acmicpc.net 💡 풀이 방식 #브루트포스 #시뮬레이션 N의 최대 크기가 50이어서 O(N^4)해도 괜찮으므로 브루트포스 가능. 대피소 갯수를 3개로 정하고 코드를 짜는 것이 핵심! 대피소가 1개인 경우는 3개 위치를 모두 동일하게 하고, 2개인 경우는 2개 위치 idx만 동일하게 하면 된다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

📖 문제 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 💡 풀이 방식 • 백트래킹 부분집합 (재귀) 을 활용해 팀을 나누고, 각 팀별로 능력치를 합하고 그 차이를 최솟값과 비교해 정답으로 출력한다. 💥 유의사항 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다. → 부분집합 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ..

📖 문제 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 💡 풀이 방식 • 브루트포스 + 백트래킹 1~N개의 재료(브루트포스) 조합을 만들면서(백트래킹), 원하는 갯수만큼 뽑힌 재료들의 (신맛 - 쓴맛)의 차이를 가장 작은 요리의 차이와 비교해 갱신한다. 1~N까지 N번 백트래킹을 실행한다. DFS의 인자는 아래와 같다. 재료를 뽑을 때마다 신맛과 쓴맛 인자를 갱신해 사용 가능하다. DFS(사용할 재료 idx, 지금껏 사용한 재료 수 cnt, 사용할 재료 수 target, 신맛 sour,..