https://www.acmicpc.net/problem/5904N이 10^9 개로 N번째 글자를 구한다는 것이 몇 번째 수열을 구해야 하는지 감도 안잡히고 굉장히 큰 수여서 long long으로도 담지 못한다.즉, 재귀적으로 길이가 n 이상인 수열을 구해서 n번째 문자를  찾으려 한다면 절대 풀 수 없다.조금 다르게 생각해서 n번째 글자만 알면 되므로 어떤 수열에 대해 n번째 글자를 알아내는 과정을 재귀로 생각하여야 한다. 사실 다 풀고 나서야 이렇게 명료하게 말할 수 있지만 풀 때는 다음과 같은 과정을 거쳤다.수열의 길이가 n 이상인 moo 수열 구하기 -> 구현을 다 하고 보니 n이 얼마 이상 커지면 오류k번째 moo 수열 S(k)에 대해 S(k-1)의 길이를 알면 S(k)를 알 수 있음. 그럼 길..

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

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번을 다시 깰 수 있다. 헷갈릴 것 같아서 이 조건은 먼저 기억해 두자. 문제의 조건을 따라서 계란을 깨다 보면 백트래킹 형태로 상태 공간 트리를 만들면서 구현하게 될 것 같다...

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 예제 8 ans : 92 백트래킹에 익숙하지 않은 분들은 [알고리즘] 백트래킹 - 재귀를 통한 구현과 응용 문제 백트래킹을 공부하기 전에 BFS와 재귀를 꼭 꼭 먼저 공부하는 것을 추천합니다. 구현의 상당 부분이 재귀로 이루어지고 BFS와 비슷한 이론의 느낌이 나기 때문입니다. [알고리즘] BFS와 DFS BFS는 큐 jun-n.tistory.com 이 글을 꼭 먼저 읽어보시기 바랍니다. 먼저 적당히 4개 정도의 퀸을 손으로 놔보자. 처음에 퀸 하나를 0행 0열에 두고 밑으로 ..