백준 문제풀이/BRUTE FORCE
-
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 5650 : [모의 SW 역량테스트] 핀볼 게임백준 문제풀이/BRUTE FORCE 2020. 6. 2. 23:38
문제 문제 풀어보기 풀이 진짜 우리는 이 난독증을 어떻게 헤쳐나가야 할까. SWEA 문제는 안 되는 테스트 케이스 위주로 설명을 해보겠습니다. 자신이 이것까지 확인했는지 확인해보세요. 1. 블록홀과 웜홀을 없을수도 있다. 2. 오직 빈공간에서만 시작한다. 3. 블록의 수평수직면을 맞으면 반대방향으로 이동한다. 4. 벽을 맞아도 점수를 얻는다 (case 3) 저는 문제에 다 적혀있는걸 항상 놓치게 됩니다. 어렸을 때 책을 많이 읽으라는게 괜히 하는 소리가 아닌가 봅니다. 코드 #include #include #include #include #include #include using namespace std; #define safe(x,y) (x>=n || x ans) ans = score; break; }..
-
SWEA 2105 : [모의 SW 역량테스트] 디저트 카페백준 문제풀이/BRUTE FORCE 2020. 5. 29. 20:26
문제 문제 풀어보기 풀이 이 문제는 완전 탐색 문제입니다. 우선 탐색을 시작할 시작점의 좌표를 정하는 FOR문 두 개 두 대각선의 길이를 정하는 FOR문 두 개를 메인에서 정해줍니다. 그리고 그 조건으로 문제를 푸는 거죠. 허접하지만 이해를 돕기 위해 그림을 그려보면 저는 시작점을 왼쪽 끝에 있는 파란 동그라미로 잡았습니다. 시작점을 어느 점으로 정 하냐에 따라 순서가 조금씩 달라질 수 있습니다. 그리고 두대 각선의 길이는 빨간색선으로 표시했습니다. 굉장히 유사한 문제를 가져왔습니다. https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재..
-
SWEA 1244 : [S/W 문제해결 응용] 2일차 - 최대 상금백준 문제풀이/BRUTE FORCE 2020. 5. 20. 15:29
문제 문제 풀어보기 풀이 재귀를 돌면서 모든 경우를 탐색하는 것은 굉장히 기본적인 완전 탐색 방법입니다. 하지만 이상하게 교환횟수가 7개 정도만 넘어가면 계속해서 시간초과가 뜨더군요. 생각해봅시다. 주어지는 수는 최대 6자리의 숫자입니다. 여기서 두개의 인수를 교환해서 원하는 숫자를 얻기 위해서는 최대 몇번의 교환이 필요할까요? 카드게임을 예를 들어 봅시다. 도둑잡기, 원카드, 훌라 어떤 게임이든 상관없이 손에 6장의 카드가 있습니다. 우리는 이 카드를 정리하기 위해 한 카드 씩 원하는 위치에 가져다 놓습니다. 이 과정은 두 개의 위치를 교한 하는 것과 크게 다르지 않습니다. 그리고 우리는 정확히 카드의 개수만큼 교환할 수 있다면 어떤 순서의 배열이든 만들 수 있습니다. 그렇기 때문에 이 문제에서도 재귀..
-
BOJ 15686 : 치킨 배달백준 문제풀이/BRUTE FORCE 2020. 3. 1. 16:43
문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아래와 같은 지..
-
BOJ 2143 : 두 배열의 합백준 문제풀이/BRUTE FORCE 2020. 2. 12. 22:35
문제 한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오. 예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다. 입력 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000..
-
BOJ 13460 : 구슬 탈출 2백준 문제풀이/BRUTE FORCE 2020. 2. 6. 13:43
문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으..
-
BOJ 14391 : 종이 조각백준 문제풀이/BRUTE FORCE 2020. 1. 30. 15:05
문제 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다. 영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다. 아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다. 각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다. 종이를 적절히 잘라서 조각의..