겜돌이의 개발일지

문제 백준 1038 감소하는 수 C++ 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 감소하는 수의 순서는 다음과 같습니다. 한 자리 : 0 (0번째) -> 1 (1번째) ~ ... ~ 9 (9번째) 두 자리 : 10 -> 20 -> 21 -> 30 -> 31 -> 32 -> ... -> 98 세 자리 : 210 > 310 -> 320 -> 321 -> ... -> 987 네 자리 : 3210 -> ... -> 9876 ... 열 자리 : 9876543210 각 자리 수가 0~9 이기 때..

문제 백준 17471 게리맨더링 C++ 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 N까지의 노드를 0과 1로 양분합니다. 0과 1을 양분할 수 있는 모든 경우의 수에 대해 실행합니다. (조합 이용) 0과 1로 양분할 수 있게 영역이 결정되면, 각 영역을 서로 0은 0끼리, 1은 1끼리 연결할 수 있는지 확인힙니다. 연결이 가능하다면, 각각의 합을 구한 후 차를 구하고, 최솟값과 비교하여 갱신합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..

문제 백준 14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 처음에 모든 블록을 하드 코딩하려다가 뭔가 잘못된 것을 깨닫고 풀이를 참조했습니다. ㅓ, ㅏ , ㅜ, ㅗ 모양을 제외한 테트로미노는 시작 지점을 깊이가 0이라고 했을 때, 깊이가 3인 dfs로 표현할 수 있습니다. ㅓ, ㅏ , ㅜ, ㅗ 모양은 하드 코딩(elseshape)으로 따로 점검해줍니다. map을 돌면서 해당 지점에서 만들 수 있는 테트로미노의 최댓값을 저장하고, maxsum을 넘는다면 maxsum을 바꿔줍니다. 모든 map을 다..