작심 24/7

3085번: 사탕 게임 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다. www.acmicpc.net 1. 교환 전에 먼저 모든 행과 열을 한 번씩만 탐색해주며 최댓값을 찾는다. 2. 사탕을 교환하고 그때 값이 바뀌는 행과 열에서 가장 긴 연속 부분을 탐색한 뒤 교환 전으로 다시 되돌려 놓는 방식을 반복해서 최댓값을 찾는다. 교환은 두 가지 종류를 해줘야 하는데, 첫 번째는 행 교환이다. 이때 값이 바뀌는 열 2개랑 행 1개를 탐색해서 최댓값을 업데이트한다. 두 번째는 열 교환이다. 마찬가지로 이때 값이 바뀌는 열 1개랑 행 2개를 탐색해서 최댓값을 업데이트한다. import java.util.Scanner; public class BOJ_3085_사탕게임 { static int max =..

17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 1. 가로 2. 세로 3. 대각선 현재 위치는 항상 0번이고 가로일 땐 1, 3번 세로일 땐 2, 3번 대각선일 땐 1, 2, 3번으로 이동할 수 있다. 이 패턴을 이용해 이전에 어느 방향이었는지와 현재 위치를 넘겨주며 재귀 호출로 완전 탐색을 구현하면 된다. #include using namespace std; int N, d, res; int arr[17][17], dx[3] = { 0, 1, 1 }, dy[3] = { 1, 0, 1 ..

17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름�� www.acmicpc.net 경계의 길이 d1과 d2의 길이가 각각 1부터 N-1까지일 때 만들 수 있는 꼭짓점 A, B, C, D를 기준으로 나누어진 1, 2, 3, 4, 5 선거구의 인구수를 구해야 한다. 한 칸을 꼭짓점 A라 할 때, 이 점을 기준으로 나머지 꼭짓점 B, C, D도 만들어 최소 한 번이라도 다섯 선거구로 나눌 수 있는 조건을 만족시키는 칸은 파란색 경계선 안의 칸들이다. 빨간색으로 표시된 칸들은 B, C, D 세 점 모두를 만들 수 없는 경우 즉, 다이아몬드 모양의 경계선..

9202번: Boggle 문제 상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 상근이는 한 번도 부인을 Boggle�� www.acmicpc.net 단어 사전을 만들 때 트라이 알고리즘을 이용하여 트리를 만들면 트리 생성 시 O(L*M), 탐색 시 O(L) (L : 제일 긴 문자열의 길이, M : 총 문자열의 수) 로 빠르게 문자열을 탐색할 수 있다. Boggle 보드의 모든 칸마다 가로, 세로, 대각선으로 인접한 칸을 DFS로 글자 수 1부터 8까지 탐색한다. 탐색하면서 사전에 이 단어가 있는지 찾는데 해당 단어가 있다면 set에 있는 단어인지 체크해준 뒤 (중복 찾기 방지 위해) s..

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 블록을 옮기는 방향에 따라 다르게 검사하며 1. 위로 옮길 때 -> 각 열 위에서부터 검사 2. 아래로 옮길 때 -> 각 열 아래에서부터 검사 3. 왼쪽으로 옮길 때 -> 각 행 왼쪽에서부터 검사 4. 오른쪽으로 옮길 때 -> 각 행 오른쪽에서부터 검사 같은 숫자가 연속해서 나오면 (빈칸 무시) 그 두 숫자를 더한 값을 큐에 넣고 같은 숫자가 연속하지 않을 때는 그 숫자만 큐에 넣는다. 한 줄의 검사가 끝나면 큐에 있는 숫자를 보드판에..

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net ▷다른 방식 풀이 보러가기 상, 하, 좌, 우 방향으로 굴리면서 DFS 한다. 빨간 구슬과 파란 구슬이 일직선 상에 있을 경우 order 함수를 통해서 어느 구슬 먼저 굴려야 할지 판단해준 뒤 그 순서에 따라서 다음 경우에 맞게 처리해준다. 1. 빨간 구슬이 구멍에 들어가건 안 들어가건 상관없이 파란 구슬이 구멍 안으로 들어가는 경우 -> 실패이므로 구슬들의 위치만 원 상태로 복귀 후 다음 방향으로 넘어감(cont..

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 완전 탐색, DP 두 가지 방법으로 풀 수 있다. 완전 탐색은 1일부터 차근차근 가능한 날을 모두 골라 최댓값을 구해주면 되고 DP는 i 일에 얻는 이익 = max(i 일을 선택할 때 얻는 최대 이익, i 일을 선택하지 않을 때 얻는 최대 이익) → i 일에 얻는 이익 = max(i 일을 선택할 때 얻는 이익 + i+T[i]일에 얻는 최대 이익, i+1일에 얻는 최대 이익) → DP[i] = max(P[i] + DP[i + T[i]], DP[i + 1]) 라는 점화식을 세워주고 재귀로 구현하면 된다. 1. 완전 탐색 #include #include using namespace std; int N, M..

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 모양별로 나올 수 있는 모든 경우를 그려보고 중복되는 부분만 연산으로 저장해두려다 이렇게 푸는 게 아닌 거 같아서 검색해보니 이 4가지 도형을 회전, 대칭시킨 모든 경우가 DFS로 깊이 4만큼 탐색하는 경우와 같다는 것을 알게 되었다. (개소름) 나머지 도형 하나는 중앙 칸을 기준으로 하좌우, 상좌우, 상하우, 상하좌 로 뻗어있는 모양을 가질 수 있고 이 4가지의 경우의 수는 상하좌우를 순서 상관없이 3가지를 뽑은 경우이므로 조합으로 구해주면 된다. #inclu..