![]()
📖 문제 https://www.acmicpc.net/problem/18429 💡 풀이 방식• DFS (조합)백트래킹으로 운동 키트 번호를 뽑는다. (중복 X)뽑은 운동 키트를 순서대로 돌면서, 중량이 모두 500 이상인 경우만 정답 +1을 한다. 🔺 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556import java.util.*;import java.io.*; public class Main { static int N,K,answer; static int[] arr; static boolean[] chk; static ListInt..
![]()
📖 문제 https://www.acmicpc.net/problem/7490 💡 풀이 방식• 브루트포스 + 백트래킹 + 문자열 [DFS 함수]- 인자: now - 현재 탐색 중인 숫자의 위치 (1부터 시작) / num - 현재 숫자 / sign - 현재 숫자의 부호 (1이면 +, -1이면 -) / sum - 현재까지의 합계 / str - 현재까지의 연산식- 종료 조건: 수열의 맨 마지막 숫자 N에 도달했을 경우- 부호가 [공백이냐/+냐/-냐] 에 따라 재귀함수를 호출한다. 🔺 코드1234567891011121314151617181920212223242526272829303132333435import java.util.*;import java.io.*; public class Main { ..
![]()
📖 문제 https://www.acmicpc.net/problem/16945 💡 풀이 방식• 백트래킹1. 3x3 배열에 모든 숫자 1-9를 중복되지 않게 나열한다.2. 나열 후, 해당 배열이 매직 스퀘어( = 가로,세로, /, \의 합이 모두15인지) 확인한다.3. 매직 스퀘어인 경우, 최솟값을 갱신해 정답을 구한다. 🔺 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071import java.util.*;import java.io.*; public class Main { static int[][]..
![]()
📖 문제 https://www.acmicpc.net/problem/12100 💡 풀이 방식• 백트래킹 + 시뮬레이션 백트래킹으로 상하좌우 4방향에 대해 5회까지 다 이동시켜보고, 배열 내 가장 큰 수를 구한다. 🔸 void DFS(명령 횟수)[종료 조건] 명령 횟수가 5번인 경우, 배열 내 최댓값을 탐색하고, 이를 최댓값과 비교해 최댓값 갱신if(cnt == 5) { findMax(); return;} 그게 아닌 경우, 과정 1,2를 진행한다. 1) 원본 배열 map을 복사한다.int[][] copy = copyArray(map); 2) 상하좌우 4방향 중 이동 방향을 정하고, 해당 방향으로 이동시키고, 명령 횟수에 +1해 재귀호출을 진행한다. 그리고 이동시켰던 배열 값을 원상복구..
![]()
📖 문제 https://www.acmicpc.net/problem/16943 💡 풀이 방식• 백트래킹 백트래킹으로 정수 A에 포함된 숫자들의 순서를 섞어 숫자 C를 만든다.이렇게 만든 숫자가 0으로 시작하지 않고, B보다 작은 경우, 정답과 비교해 더 큰 값으로 정답을 갱신한다. 💥 유의사항새롭게 만든 C를 문자열로 봤을 때 0으로 시작하는지 확인해야 한다. 🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657import java.util.*;import java.io.*; public class Main { static String[] st..
![]()
📖 문제 https://www.acmicpc.net/problem/14620 💡 풀이 방식• 브루트포스 + 백트래킹1. 격자를 입력받는다.2. 완전탐색으로 모든 점을 확인한다. 해당 지점에서 꽃을 심을 수 있는 경우, 해당 자리와 상하좌우 자리에 대해 꽃을 심어보고, 뽑은 갯수를 +1하고, 비용을 더한 후 재귀호출한다. 그리고 다음 탐색을 위해 해당 자리와 상하좌우 자리에 대해 값을 초기화한다. [x행 y열 위치에서 꽃을 심을 수 있는지 확인하는 함수 : boolean isPossible(int x, int y)]꽃을 심을 수 있는 조건 - 방문한 적 없어야 함 - 4방향 탐색 시 - 꽃잎이 배열 화단 범위를 벗어나선 안 됨 - 꽃잎 자리에 다른 꽃이 핀 경우(visited..
![]()
📖 문제 https://www.acmicpc.net/problem/9944 💡 풀이 방식• 백트래킹1. 값을 입력받으면서 격자 안의 값이 장애물(*)인 경우, 방문 처리하고 방문한 칸의 갯수(cnt)를 1 증가시킨다.2. 한 칸만 빈 칸인 경우, 해당 케이스의 이동 경로 수는 0이다.if(cnt == N*M) answer = 0; // 한 칸만 빈 칸인 경우 3. 모든 칸을 탐색하며 방문한 적 없는 점에서,4방향 탐색을 통해 1) 격자 범위 내에 있고, 2) 방문하지 않은 칸을이동 처리했다가 안 했다가 하며 이동 경로 수를 구한다. (백트래킹)for(int i = 0 ; i [백트래킹 함수]- 인자 : x좌표, y좌표, 이동 횟수(result), 방향 번호(dir), 방문 갯수(cnt)s..
![]()
📖 문제 https://www.acmicpc.net/problem/16938 💡 풀이 방식• 백트래킹+ 브루트포스1. 문제들을 배열에 입력받고, 이 배열을 난이도 기준 오름차순 정렬한다.2. 2~N개까지 캠프에 사용할 문제들을 고른다. (백트래킹)for(int i = 2 ; i [백트래킹 함수] - (종료 조건) 목표 갯수만큼 뽑았다면, 문제에서 제시한 2가지 조건을 만족하는지 확인하고 방법 수를 갱신한다.(여기서 리스트를 오름차순 정렬하지 않는 이유는, 이미 배열을 입력받고 오름차순 정렬해두어서 리스트에 저장할 때 이미 오름차순으로 난이도를 저장해 두기 때문이다.)if(cnt == target) { int sum = 0; List list = new ArrayList(); ..
![]()
📖 문제 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(↕↔)인 경우 : 북남서동(..
