💡 Problem Solving

[백준 - 1780] 종이의 개수 [C++]

1. 문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 2. 풀이과정 문제에서 주어진 규칙대로 해결하면 된다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. [코드설명] check함수는 (y, x)를 좌측상단 꼭짓점으로 하고 한 변의 길이가 distance인 정사각형이 모두 같은 수로 이루..

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

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

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