브루트포스(7)
-
백준 1018번: 체스판 다시 칠하기 (C++)
https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 완전 탐색 문제. 전부 체크해야만 알 수 있는 문제인데 체크 방법을 고민했다. 나는 B로 시작하는 체스판과 W로 시작하는 체스판을 미리 만들어 놓고 비교하는 식으로 구현했다. 어처피 8 * 8이라서 시간 복잡도 문제가 생기지 않을 거 같았고 B, W 보드와 비교 후 둘 중 작은 값을 갱신해가며 탐색을 진행했다. 전체 코드 #include #include using namespace s..
2023.01.26 -
백준 13140번: Hello World! (C++)
https://www.acmicpc.net/problem/13140 13140번: Hello World! N이 주어질 때 hello + world = N을 만족하는 서로 다른 한 자리 자연수(0 포함) d, e, h, l, o, r, w를 구해서 아래 그림과 같은 형태로 출력하는 프로그램을 작성하여라. 단, h와 w는 0이 될 수 없다. www.acmicpc.net 풀이 오늘 순열로 현타오게 만든 문제. 완전 탐색인건 알고 접근했으나 무지성 for 문과 if 문을 남발하던 도중 이건 아니다 싶어서 찾아봤다. 순열로 너무 간단하게 풀리는 것을 보고 조금 충격이었다. unordered_map을 이용해 helowrd에 해당하는 value를 계속 변경하는 방법이다. 순열로 변경하기 때문에 모든 조건을 탐색할 수..
2023.01.21 -
백준 2309번: 일곱 난쟁이 (C++)
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 풀이 그냥 완전 탐색으로 풀어도 되지만 순열 연습용으로 풀었다. 우선 난쟁이들을 정렬하고 순열을 돌려주었다. 그리고 앞의 7명의 값을 더했을 때 100이 되면 종료시키는 방법으로 구현했다. 전체 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int Dwarf[9]; i..
2023.01.21 -
백준 2890번: 카약 (C++)
https://www.acmicpc.net/problem/2890 2890번: 카약 첫째 줄에 R과 C가 주어진다. 다음 R개 줄에는 '.', 'S', 'F', '1'~'9'로 이루어진 위성 지도가 주어진다. 한 줄에는 최대 한 개의 카약만 있고, 위성 사진에 있는 카약은 항상 9개이다. (10 ≤ R, C ≤ 50) www.acmicpc.net 풀이 완전 탐색으로 진행해도 R * C, 즉, 최대 50 * 50 정도 밖에 들지 않기 때문에 완전 탐색으로 진행했다. String 백터를 이용하여 문자열을 입력 받았고 결승선 F와 가장 가까운 부분(C - 2)부터 차례대로 탐색했다. rank 변수를 이용해 카운트를 받아주었고 어떤 레일도 순위에 들지 않을 때는 카운트가 증가되지 않도록 구성했다. 전체 코드 #..
2023.01.19 -
백준 1057번: 토너먼트 (C++)
https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 kim과 im의 번호를 뺏을 때 1이고 그 중 큰 번호가 짝수일 때 둘이 만나는 라운드다. 이 법칙에 따라 while문의 내용을 넣어주었고 kim과 im을 계속 2로 나누어서 진행시켰다. while문을 탈출하면 둘이 만나는 라운드기 때문에 round를 출력시켰다. 간단하게 구성한 줄 알았는데 문제를 풀고 다른 블로그를 찾아보니 조금 더 간단하게 구성한 while문이 있었다. kim을 2로 나눌때 3..
2023.01.17 -
백준 1051번: 숫자 정사각형 (C++)
https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 풀이 완전 탐색인 듯해서 시간복잡도를 계산해보니 50*50*50정도 밖에 나오지 않았다. 그냥 완전 탐색을 돌려주었다. 전체 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, M; int ans = 1; int board[51][51]..
2023.01.17