백준

[백준 - 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..

[백준 - 15658] 연산자 끼워넣기 (2) [C++]

1. 문제 https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 2. 풀이과정 모든 수의 사이에 연산자를 끼워 넣을 수 있는 모든 경우에 대해서 식의 결과의 최대, 최소를 구한다. [코드설명] dfs함수는 모든 수의 사이에 연산자를 끼워 넣을 수 있는 모든 경우에 대해 탐색한다. 주의해야 할 점은 최대값, 최소값을 저장하는 변수의 초기값을 잘 설정해줘야 하는 것이다. 연산자를 어떻게 끼워넣어..

[백준 - 15666] N과 M (12) [C++]

1. 문제 https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 풀이과정 N과 M (11)문제에서 아래의 조건만 추가된 문제이다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다 N과 M (11) 설명 : https://poisson-it.tistory.com/28 [코드설명] N과 M (11)코드에 한줄만 추가해주면 된다. dfs함수내에서 if(v...

[백준 - 15665] N과 M (11)

1. 문제 https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 풀이과정 1. N개의 자연수 중에서 M개를 고른 수열 2. 같은 수를 여러 번 골라도 된다. 3. 중복되는 수열을 여러 번 출력하면 안 된다. 4. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 위의 네 가지 조건을 만족해야한다. 3번 조건을 만족하기 위해 같은 레벨에서 같은 수를 중복 방문하지 않아야한다. 4번 조건을 만족하기 위해 N개의 수를 오름차순 정렬해줘야한다. ..

[백준 - 15664] N과 M (10) [C++]

1. 문제 https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 풀이과정 N과 M (9)문제에서 아래의 조건만 추가된 문제이다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다 N과 M (9) 설명 : poisson-it.tistory.com/23 [코드설명] N과 M (9)코드에 한줄만 추가해주면 된다. dfs함수내에서 if(v.size() && v..