https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 기본적인 백트래킹 + 브루트포스 문제이다. 가능한 모든 경우의 수를 해보면서 최댓값을 찾으면 된다. 순열 구하는 문제와 동일하다. 만일 아직 백트래킹이 잘 이해가 되지 않는다면, 아주 작은 테스트 케이스를 하나 만들어서 직접 손으로 코드를 따라가보면 된다. 물론 당연히, 시스템 스택을 알고있어야 한다. import sys #sys.setrecursionlimit(10**6) input = sys.stdin.re..
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 백트래킹을 이용한 브루트 포싱이다. 단어의 앞뒤가 항상 anti, tica로 이루어져 있으므로 최소 5개의 글자 (a,c,i,n,t) 는 알고 있어야 한다. 그리고 이제 남은 알파벳 21개 중에서 추가로 학습을 진행한다. 이 때 알고 있는 글자의 수가 k개가 될 때 까지만 진행한다. 만약 depth가 k에 도달한다면, 입력으로 주어진 단어를 탐색하면서 모르는 글자가 나올 경우 탐색을 종료하..
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 구현 + 백트래킹 + 브루트포스 문제다. 사다리의 가로줄과 세로줄을 각각 x좌표 y좌표라고 생각하고 풀면 편할 것이다. 우선 입력을 받으면서, 가로선이 그려진 좌표를 표시해준다. (가로선이 그려질 때 (x,y)와 (x,y+1)를 잇게 되는데, 이 두 좌표를 모두 1로 표시하고 푸는 방법도 있으니 참고!) 그리고나서 탐색을 시작하는데, 매 탐색마다 i번 라인에서 출발하여 도착 결과가 i번 인지 확..
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 오랜만에 푼 구현 + 브루트 포스 + 백트래킹 문제이다. 문제 자체는 크게 까다롭지 않지만, 백트래킹에서 고민을 좀 많이 하였고 결국 다른 글을 참고하게 되었다..(시무룩) 1. 입력을 받는다 (CCTV가 나오면 해당 좌표를 벡터에 담아준다!) 2. 완전 탐색을 실시한다. 3-1. 만약 모든 CCTV를 확인하여, 감시 구역을 정했으면 사각지대의 수를 세서 최솟값을 저장한다. 3-2. 아..
