전체 글

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

1. 문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이과정 n의 범위가 (1 dp[2] = 2 - 3을 1, 2, 3의 합으로 나타내는 방법들 1 + 1 + 1 1 + 2 2 + 1 3 => dp[3] = 4; - 4를 1, 2, 3의 합으로 나타내는 방법들 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 => dp[4] = 7; 1+1+1+1, 1+2+1, 2+1+1, 3+1 이 식들은 3을 1, 2, 3의 합으로 나타내는 방법들에 1을 더해준 것이다. 1+1..

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

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