완전탐색
-
BOJ 14225 : 부분수열의 합백준 문제풀이/BRUTE FORCE 2020. 6. 5. 00:30
문제 문제 풀어보기 풀이 완전 탐색을 하는데 중복되는 계산을 줄여주는 방법을 선택합시다. 재귀 문을 보면 그냥 포문 돌면서 하나씩 다 더해보는 겁니다. 그런데 저기서 st 인자를 없애고 모두 처음부터 본다면 어마어마한 중복이 발생합니다. 예를 들어 1, 2, 3, 4의 인자가 있다면 st 인자없이 모두 처음부터 탐색을 하는 경우 이러한 순서로 탐색할 겁니다. 하지만 현재 선택한 인덱스보다 작은 인덱스를 선택하는 경우는 모두 중복 수열이 됩니다. 따라서 st 인자를 사용해서 이전 인덱스는 넘어가게 해 줍시다. 코드 #include #include #include #include #include #include using namespace std; #define safe(x,y) x>=8 || x
-
SWEA 2105 : [모의 SW 역량테스트] 디저트 카페백준 문제풀이/BRUTE FORCE 2020. 5. 29. 20:26
문제 문제 풀어보기 풀이 이 문제는 완전 탐색 문제입니다. 우선 탐색을 시작할 시작점의 좌표를 정하는 FOR문 두 개 두 대각선의 길이를 정하는 FOR문 두 개를 메인에서 정해줍니다. 그리고 그 조건으로 문제를 푸는 거죠. 허접하지만 이해를 돕기 위해 그림을 그려보면 저는 시작점을 왼쪽 끝에 있는 파란 동그라미로 잡았습니다. 시작점을 어느 점으로 정 하냐에 따라 순서가 조금씩 달라질 수 있습니다. 그리고 두대 각선의 길이는 빨간색선으로 표시했습니다. 굉장히 유사한 문제를 가져왔습니다. https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재..
-
BOJ 14391 : 종이 조각백준 문제풀이/BRUTE FORCE 2020. 1. 30. 15:05
문제 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다. 영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다. 아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다. 각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다. 종이를 적절히 잘라서 조각의..
-
BOJ 2529 : 부등호백준 문제풀이/BRUTE FORCE 2020. 1. 12. 00:28
문제 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A => 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0 이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들..
-
[Brute Force] BOJ 14500 : 테트로미노백준 문제풀이/BRUTE FORCE 2019. 9. 6. 01:41
문제(삼성 sw 기출문제) 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하..
-
[Brute Force] BOJ 1476 번 : 날짜 계산백준 문제풀이/BRUTE FORCE 2019. 6. 25. 20:08
문제 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다. 예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. ..
-
[Brute Force] BOJ 2309 번 : 일곱 난쟁이백준 문제풀이/BRUTE FORCE 2019. 6. 25. 19:22
문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 입력 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. 문제 요약 9명의 키가 모두 다른 난쟁이들이 있다. 이 중에서 키의..