본문 바로가기

Algorithm/Brute Force

 (142)
(C++) - 백준(BOJ) 8295 : Rectangles https://www.acmicpc.net/problem/8295 8295번: Rectangles The first and only line of the standard input contains three integers: n, m and p (1 ≤ n, m ≤ 100, 4 ≤ p ≤ 2(n+m)), representing the dimensions of the grid and the lower bound for the perimeter of the rectangles. www.acmicpc.net 모든 경우의 수를 탐색하는 brute force 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 세로의 크기 n, 가로의 크기 m, 최소 만족 둘레의 길이 p, 정답을 출력할 변수 ans를 선언한 후 적절히..
(C++) - 백준(BOJ) 6030 : Scavenger Hunt https://www.acmicpc.net/problem/6030 6030번: Scavenger Hunt Farmer John has scattered treats for Bessie at special places in the pasture. Since everyone knows that smart cows make tasty milk, FJ has placed the treats at locations that require Bessie to think. He has given her two numbers, P and Q (1 > q; pFactor = getFactor(p); qFactor = getFactor(q); for(auto pf : pFactor){ for(auto qf : qFactor..
(C++) - 백준(BOJ) 4108 : 지뢰찾기 https://www.acmicpc.net/problem/4108 4108번: 지뢰찾기 C개의 문자들이 포함된 R개의 줄을 출력한다. 단, 모든 '.' 대신 인접한 칸에 위치한 지뢰의 수로 변경해 출력한다. '*' 칸은 그대로 출력한다. 문자 사이에 공백이나 줄 사이에 공백 줄이 있어선 www.acmicpc.net 모든 곳을 탐색해 답을 구하는 brute force문제였습니다. 📕 풀이방법 📔 입력 및 초기화 행 r, 열 c, 지뢰상태를 입력받을 이차원 배열 board, 정답을 출력할 변수 ans를 선언 후 매 test case마다 적절히 입력받습니다. 📔 풀이과정 3가지를 수행합니다.1. board정보를 입력받습니다.2. 정답을 구합니다.현재 i행 j열이라면 i - 1행 ~ i+1행까지, j-1열 ~ ..
(C++) - 백준(BOJ) 1235 : 학생 번호 https://www.acmicpc.net/problem/1235 1235번: 학생 번호 첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부 www.acmicpc.net 모든 경우의 수를 탐색하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n, 학생번호 길이 length, ans, 학생 번호를 저장할 vector변수 students, map변수 m을 선언합니다. 📔 풀이과정 0 ~ length - 1까지 loop를 수행합니다.1. 그 안에서 n개의 학생 list를 확인하면서 뒤에 k만큼만 남긴뒤 map에 추린 학생번호를 key, key의 빈도 수를 v..
(C++) - 백준(BOJ) 18511 : 큰 수 구성하기 https://www.acmicpc.net/problem/18511 18511번: 큰 수 구성하기 첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 www.acmicpc.net 모든 경우의 수를 탐색하는 brute force문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n, k, 정답을 출력할 ans, k집합 vector setK, 순열을 뽑을 vector permutation를 선언하고 입력받습니다. 📔 풀이과정 2가지를 구현해야 합니다. 1. k개의 원소중 x개를 뽑아 순열로 만듭니다. 2. 뽑은 원소로 수를 이어 붙인 뒤 n과 비교..
(C++) - 백준(BOJ) 19947 : 투자의 귀재 배주형 https://www.acmicpc.net/problem/19947 19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net 재귀를 이용한 brute force문제였습니다. 📕 풀이방법 📔 입력 및 초기화 투자 기간 y, 초기돈 h를 선언한 후 입력받습니다. 📔 풀이과정 각 3가지의 경우에 대해 이자를 받은 후의 연도와 보유자산을 다름 함수의 인자로 넘겨 재귀형태로 호출합니다. 📔 정답출력 bruteForce()의 반환값을 출력합니다. 📕 Code backtracking처럼 구현한 방식 #include ..
(C++) - 백준(BOJ) 2246 : 콘도 선정 https://www.acmicpc.net/problem/2246 2246번: 콘도 선정 첫째 줄에 콘도의 개수를 나타내는 자연수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 콘도에 대한 정보를 나타내는 두 정수 D(1 ≤ D ≤ 10,000), C(1 ≤ C ≤ 10,000)가 주어진다. D는 그 콘도의 www.acmicpc.net 모든 경우의 수를 탐색하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 콘도의 개수 n, 정답 ans, 후보 가능 여부 can, xd, xc, d, c를 선언합니다. 📔 풀이과정 모든 경우의 수를 탐색하며 다음 조건인 경우에 후보지가 될수 없으므로 can을 0으로 만들고 loop를 탈출합니다. 1. 후보지보다 가까운데 가격도 싼 경우 2. 후보지보다..
(C++) - 백준(BOJ) 5671 : 호텔 방 번호 https://www.acmicpc.net/problem/5671 5671번: 호텔 방 번호 선영이는 집 호수에 반복되는 숫자가 있는 경우에는 그 집에 사는 사람에게 불운이 찾아온다고 믿는다. 따라서, 선영이는 838호나 1004호와 같이 한 숫자가 두 번 이상 들어있는 집에는 절대 살지 www.acmicpc.net 모든 경우의 수를 탐색하는 brute_force문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n, m, ans를 선언한 후 EOF가 나올 때까지 n, m에 입력받습니다. 📔 풀이과정 1. n이상 m이하의 범위로 for loop를 수행하며 유효한 방 번호인지 확인해줍니다. 2. 유효여부는 isValid함수를 수행해 각 자리 수 vector cnt를 지역변수로 선언하여 모든 수가 2개 미만으로 ..

티스토리툴바