brute force
-
백준 15683 감시Algorithm/BOJ 2020. 7. 16. 13:29
출처: www.acmicpc.net/problem/15683 분류: 완전탐색 접근방식 하.. 코드량이 너무 너무 너무 길었던 문제였습니다. 5개의 CCTV가 있고 각 CCTV는 90도로 회전이 가능합니다. 사각지대가 가장 최소가 되는 경우를 찾는 문제입니다. 각 CCTV 의 케이스는 1번 상하좌우 4개 2번 상하, 좌우 2개 3번 4개 4번 4개 5번 1개 입니다. 저는 CCTV를 먼저 찾아놓고 CCTV List를 다 탐색할 때 까지 DFS를 돌렸습니다. CCTV 에 케이스는 많지만 결국 지우는 건 방향에 따라 상하좌우 4가지 이므로 상하좌우 direction을 입력받는 함수를 만들어서 지우고 CCTV 타입별로 상 하 좌 우로 직접 입력해주는 방식을 사용했습니다. 더 스마트하게 풀 수도 있을 것 같은데 ..
-
백준 1107 리모컨Algorithm/BOJ 2020. 7. 16. 11:56
출처: www.acmicpc.net/problem/1107 분류: 완전 탐색 접근방식 돌고돌아 결국 순수한 완전탐색으로 해결한 문제입니다. 고장난 숫자 버튼이 주어질 때 원하는 채널을 만들기 위해 필요한 조작 횟수를 구하는 문제입니다. 조정할 수 있는 채널 중에서 원하는 채널과 가장 가까운 채널로 가서 + 혹은 - 로 조작하면 최소의 수를 구할 수 있... 을줄 알았으나, 생각보다 간단한 문제는 아니었습니다. 가장 가까운 채널을 어떻게 만들 것인가, "처음엔 수어진 숫자의 각 자리 마다 위, 아래로 가까운 수를 뽑으면 가장 가까운 수가 되겠구나." 라고 생각하고 접근했습니다. 5000 2 5 0 이렇게 주어지면, 5 와 0을 피해 가장 가까운 각 자리 수를 up, down으로 만들면, 밑으로 가장 가까운..
-
백준 14500 테트로미노Algorithm/BOJ 2020. 7. 15. 14:07
출처: www.acmicpc.net/problem/14500 분류: 완전 탐색 접근방식 주어진 5개의 테트로미노를 하나 놓을 때 테트로미노에 겹쳐지는 블록의 최대값이 얼마인지 구하는 문제입니다. 모든 경우를 다 체크하면 되겠지만 테트로미노는 회전 또는 대칭이 되기 때문에... 매우매우 귀찮습니다.. 😨 하지만 이 문제에는 귀찮음을 덜어줄 수 있는 법칙이 숨겨져 있습니다 :) 바로 ㅗ 모양을 제외한 테트로미노들은 한 점에서 dfs로 4개씩 탐색한 결과들입니다. 한 점에서 dfs로 4개의 블록을 고르면 4개의 테트로미노를 회전 대칭 시킨 모양안에 모두 포함됩니다! 대신 ㅗ 모양은 ㅗ ㅜ ㅏ ㅓ를 따로 찾아줘야 합니다. 해결방법 let nm = readLine()!.split(separator: " ").ma..
-
백준 15686 치킨 배달Algorithm/BOJ 2020. 7. 13. 18:42
출처: www.acmicpc.net/problem/15686 분류: 완전탐색 접근방식 집과 치킨집이 주어지고 집에서 제일 가까운 치킨집까지의 거리가 집의 치킨거리가 됩니다. 모든 집의 치킨 거리를 합친 값이 도시의 치킨거리가 됩니다. 치킨집을 M개 만큼 선택했을 때 최소가 되는 치킨거리를 구하는 문제입니다. 우선 집과 치킨집의 위치를 먼저 저장해두고 치킨집을 M개 골랐을 때의 치킨 거리들을 구하면 됩니다. 해결방법 let nm = readLine()!.split(separator: " ").map{Int($0)!} var board = [[Int]]() for _ in 0..
-
백준 1065 한수Algorithm/BOJ 2020. 6. 15. 14:56
출처: www.acmicpc.net/problem/1065 분류: 완전 탐색 접근방식 주어진 N보다 작은 수 중에서 각 자리수가 등차수열을 이루는 수를 찾는 문제입니다. 등차 = 1의자리 수 - 10의자리수 와 같이 구할 수 있겠죠? 1의 자리 수 = n%10 10의 자리 수 = (n%100)/10 저는 이런 식으로 구했습니다. 해결방법 func isHansu(_ number: Int) -> Bool { if number 0 { if d != n - num%10{ return false } n = num%10 num /..