dfs
-
[BOJ] #12100 _ 2048(Easy)Problem Solving/BOJ 2019. 10. 20. 22:42
[2048 (Easy)] https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 2048 게임에서 5번의 이동 후의 최대 값을 구하는 문제이다. dfs를 이용하여, 5번으로 이동할 수 있는 모든 경우의 수를 고려하여 최대 값을 구하였다. 단, 한 번의 이동에서 합쳐진 블록은 다시 합쳐지지 않는다는 것을 유의하자! [ 소스 코드 ] #..
-
[SWEA] #2112 _ 보호 필름Problem Solving/SWEA 2019. 8. 28. 22:15
[보호 필름] https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com dfs를 이용하여 모든 경우의 수를 다 돌린 후, 성능 검사에 통과하는 최소 투입 수를 구한다. dfs를 돌리는 경우는 총 세가지로 생각할 수 있다. 1. 약품 주입 X 2. A 약품 주입 3. B 약품 주입 [ 소스 코드 ] #include #include #include using namespace std; int D, W, K, injCount; vector film; void solve(int count, int idx); int ..
-
[BOJ] #14888 _ 연산자 끼워넣기Problem Solving/BOJ 2019. 8. 28. 21:36
[연산자 끼워넣기] https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 연산자의 순서를 모든 경우의 수로 다 계산한 후 최대, 최소 값을 구하는 문제이다. 간단하게 next_permutation을 이용하여 구현하였다. 처음에 MAX 값을 999999로 설정하였으나, 틀렸다. 출력을 읽어보면, 범위가 -10억 ~ 10억이라고 되어있다. (문제를 똑바로..
-
[BOJ] #14501 _ 퇴사Problem Solving/BOJ 2019. 8. 28. 21:25
[퇴사] https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dfs를 이용하여 모든 경우의 수를 해보고, 최대 수익을 구하였다. 찾아보니 DP를 이용해 풀 수도 있다. [ 소스 코드 ] #include #include #define MAX 15 using namespace std; int N, T[MAX + 1], P[MAX + 1]; int result = 0; void solve(int day, int TotalPrice); int main() { scanf("%d", &N); for (int i = 1; i N) { result = max(result, TotalPrice); r..
-
[BOJ] #2468 _ 안전 영역Problem Solving/BOJ 2019. 8. 28. 20:03
[안전 영역] https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어 www.acmicpc.net bfs나 dfs를 이용하여 안전한 구역의 개수를 세는 문제이다. [ 소스 코드 ] #include #include #in..