브루트포스

[백준 - 7490] 0 만들기 [C++]

1. 문제 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 2. 풀이 전형적인 브루트포스 문제이다.. 나의 경우 두번 '출력 형식이 잘못되었습니다' 를 받았었는데.. '각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.' 이것을 간과한채 제출했었다.. 케이스별로 한 줄씩 띄워주니까 맞았다.. 문제는 연산자 3개로 표현가능한 모든 식을 만들어보고 그 식을 계산했을 때 0인지 판정하면된다. c++에는 eval함수가 없어서 직접 구현했다.. 3. 코드 #include #include #include #..

[백준 - 18111] 마인크래프트 [C++]

1. 문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 2. 풀이 높이를 기준으로 완전탐색을 해보면된다. 처음에는 0~256까지 모든 높이에 대해 탐색을 했더니 70퍼센트에서 계속 틀렸었다. 로직에는 문제가 없었으나 높이의 탐색 범위가 문제였다. 그래서 탐색의 최대 높이(maxPossibleHeight)를 설정했더니 맞았다. 틀렸던 이유) 지형의 높이를 균등하게 맞추기 위해서는 평균 높이 이상으로 설정할 수 없다. 만약 평균 높이보다 더 ..

[백준 - 1051] 숫자 정사각형 [C++]

1. 문제 https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net 2. 풀이과정 N*M크기의 직사각형에서 만들 수 있는 모든 정사각형에 대해 꼭짓점에 쓰여 있는 수가 모두 같은지 확인하며 정사각형 넓이의 최대값을 구해준다. [코드설명] check함수는 특정 점 (y, x)을 좌측상단 꼭짓점으로 하고 조건을 만족하는 정사각형의 넓이들 중 최대값을 반환해준다. (조건 : 꼭짓점에 쓰여 있는 수가 모두 같아야 함) 가능한 모든 (y, x)조합에 대해 c..

[백준 - 12101] 1, 2, 3 더하기 2 [C++]

1. 문제 https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 2.풀이과정 문제의 설명대로 정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하면 된다. 4를 1, 2, 3의 합으로 나타내는 방법을 사전순으로 정렬하면 아래와 같다. 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 [코드설명] dfs함수는 n을 1, 2, 3의 합으로 나타내는 경우의 수를 생성하며 k번째로 오는 식을 출력한다. 3. 코드 #inc..

[백준 - 14500] 테트로미노 [C++]

1. 문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 2. 풀이과정 문제에서 주어지는 N×M 종이 위에 테트로미노 하나를 놓을 수 있는 모든 경우를 탐색하며 테르토미노가 놓인 칸에 쓰여있는 수들의 합을 계산해 최대값을 구한다. 처음 문제를 풀 때 가장 단순한 방법으로, 5개의 테트로미노를 배열로 나타낸 후 각각 직접 회전, 대칭시키며 가능한 모든 경우를 탐색해보았는데 시간초과가 났다. 사실 테트로미노의 모양을 보면, ㅜ모양을 제외하고 나머..

[백준 - 14501] 퇴사 [C++]

1. 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 2. 풀이과정 백준이가 상담을 잡을 수 있는 모든 경우에 대해 수익을 계산해 최대 수익을 구한다. 위와 같은 입력을 예로 들면 (1일, 4일, 5일) (1일, 5일) (2일) (3일, 4일, 5일) (3일, 5일) . . 와 같은 순서로 상담을 잡을 수 있는 모든 경우를 따져보면 된다. [코드설명] dfs함수는 상담을 잡을 수 있는 모든 경우에 대해 최대수익을 갱신해준다. 3. 코드 #include #include #include using namespace std; int n; vector T, P; bool visite..