와드의 블로그

문제크기가 N×M인 격자판의 각 칸에 정수가 하나씩 적혀 있습니다. 이 격자판에서 칸 K개를 선택하려고 합니다. 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하는 프로그램을 작성하는 문제입니다. 단, 선택한 두 칸이 인접하면 안 됩니다. (상하좌우로 붙어있는 칸은 인접한 칸으로 간주합니다.)입력: 첫째 줄에 N, M, K가 주어집니다. (1 ≤ N, M ≤ 10, 1 ≤ K ≤ min(4, N×M)) 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어집니다. (각 수는 -10,000 이상 10,000 이하)출력: 선택한 칸에 적힌 수를 모두 더한 값의 최댓값을 출력합니다.풀이: 2차원 조합 탐색을 활용한 인접 방지 백트래킹단순히 K개의 칸을 순열로 고르면 겹치는 조합이 너무 많아 시간 초과가 ..

문제1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있습니다.123456789101112131415...이렇게 만들어진 새로운 수는 총 몇 자리 수인지 구하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 N (1 ≤ N ≤ 100,000,000)이 주어집니다.출력: 첫째 줄에 새로운 수의 자릿수를 출력합니다.링크: https://www.acmicpc.net/problem/1748풀이: 자릿수의 기여도(Contribution)를 활용한 수학적 최적화N이 최대 1억이므로 1부터 N까지 순회하며 문자열을 이어 붙이거나 자릿수를 일일이 더하면 무조건 시간 초과가 발생합니다. 이 코드는 '각 숫자가 전체 자릿수에 몇 번 기여하는가?'를 수학적으로 분해하여 단 몇 번의 연산만으로 정답..

문제크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 합니다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있습니다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어집니다. (4 ≤ N, M ≤ 500) 둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어집니다.출력: 테트로미노가 놓인 칸의 수들의 합의 최댓값을 출력합니다.링크: https://www.acmicpc.net/problem/14500풀이: 전역 방문 배열을 활용한 백트래킹 완전 탐색DFS와 백트래킹: 임의의 칸에서 시작하여 상하좌우로 4번 연속 이동(DFS)하면, 테트로..