14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제를 분석하다 가장 먼저 떠오른 풀이는 백트래킹이었다. N이 최대 15이므로 최대 가능한 상담이 2^15개로 계산된다. 그리고 각 경우의 수당 이익을 계산하는 것과 백트래킹 하는 과정은 상수 시간이 소모될 것 같아서 가능하다 판단하고 백트래킹으로 구현을 시작했다. 구현이 조금 막막하게 느껴질 수 있는데, 일단 모든 경우의 수를 판단해야 한다. 대충 트리를 만들어보자면 이런 형태를 띤다. 트리대로 구현하면서 가지치기를 해주면 될 것 같다. 이런 느낌의 완전탐색은 재귀로 구현하면 비교적 쉽다. 재귀로 구현하고 재귀식 내부에서 백트래킹을 해주는 걸로 하고 구현해 보자. 재귀를 구현할 땐 아래의 세 부분을..

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 예제 5 5 1 2 3 4 5 5 4 3 2 1 2 3 4 5 6 6 5 4 3 2 1 2 1 2 1 ans : 19 문제 분석부터 해보자. 테트로미노라는 블록을 보드에 넣는데, 블록이 들어가는 칸의 합이 가장 크게 되는 숫자를 찾으면 된다. 테트로미노는 총 5 종류고, 가장 먼저 떠오르는 방법은 모든 테트로미노를 하나하나 끼워 넣는 방법이다. 보드의 크기가 2500이고 블록 단 한 개만 넣으면 되므로 모든 테트로미노를 다 끼워보는 방법으로 구현해도 될 것 같다...

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 분석부터 해보자. N * M 크기 보드에 파란 구슬, 빨간 구슬이 하나씩 있고 상하좌우 기울여서 구슬이 구멍에 들어가는지 관찰하면 된다. 빨간색만 빠지면 성공이고 빨, 파 동시에 빠지거나 파란색만 빠지면 실패이다. 10번 이상 움직여도 실패이다. 문제를 보고 예제들을 한 번 훑어보면서 생각난 주의 사항은 다음과 같다. 공 하나가 구멍에 빠지는 경우를 주의하자. (예제 7) 움직일 때 두 공이 겹칠 수 없다. ..

2023.10.25 - [알고리즘/문제풀이] - [BOJ] C++ 15655 N과 M (6) - 제한이 까다로운 백트래킹 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 예제가 굉장히 많아 백준에서 참고하시길 바랍니다. 주의할 점은 백준의 test case에는 4번 cctv에 대한 검증이 부족하므로 개인적으로 테스트해볼 것을 추천합니다. 먼저 문제는 최대 8 * 8 크기에 최대 8개의 cctv 각 cctv는 최대 4방향이므로 4^8 = 65536이다. 따라서 완전탐색으로도 충분히 시간안에 풀 수 있을..

16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 예제가 굉장히 많아 백준에 들어가서 보시는 것을 추천합니다! 굉장히 재미있는 문제인데, 데이터의 수가 8로 굉장히 적다. 완전 탐색을 먼저 고려해 보고 문제에서 시키는 조건대로 알고리즘을 생각해 보자. 문제를 풀다가 알게 된 건데 1번 계란으로 3번을 깬 후 3번 계란으로 1번을 다시 깰 수 있다. 헷갈릴 것 같아서 이 조건은 먼저 기억해 두자. 문제의 조건을 따라서 계란을 깨다 보면 백트래킹 형태로 상태 공간 트리를 만들면서 구현하게 될 것 같다...

오늘은 백트래킹 문제를 하나 풀었다. 백트래킹을 정석적인 재귀로만 생각한다면 절대 풀 수 없는 문제였다. 백트래킹을 너무 어렵게 생각해 왔던 것 같은데, 상태 공간 트리를 만들면서 가지치기해주기만 기억하면 될 것 같다. 쉽게 말하면 한 번 가지 끝까지 가보고 안되면 에코 궁 써서 돌아오기 정도로 생각하면 될 것 같다.