본문 바로가기

백준플래/Backtracking2

백준 1133, 반복되지 않는 단어 개요 문제 링크 플래 5, 백트래킹 부분문자열이 K번 이상 반복되지 않으며 A개의 문자만 사용한 길이 N의 문자열 출력 접근 재미난 백트래킹 문제, 백트래킹이라는 것을 알면 크게 어렵지 않다. 백트래킹의 핵심 세 가지는? 가능여부, 마지막 단계, 다음단계. 마지막단계는 길이가 N일 때이다. 가능여부를 미리 체크한다면 마지막 단계는 항상 가능하므로 바로 출력하고 1을 return한다. 다음단계로 넘어가는 조건은 뭘까? A부터 A개의 문자를 우선 집어넣어본다. 그리고 K번의 반복된 문자열이 있으면 다음단계로 가지 않으면 된다. 반복된 문자열이 없으면 되는데, 크게 어렵지 않다. 우리에겐 C++의 미친 장점, substr이 있기 때문이다. 길이가 1인 것부터 체크한다. 만약 n이 (길이)×k보다 작다면 k개의.. 2023. 3. 7.
백준 13200, Light Up 개요 문제 링크 플래 3, 백트래킹 네 방향으로 진행하는 빛이 겹치지 않도록, 검은 점 주변에 숫자만큼의 전구를 배치하기 접근 까다로운 구현문제, 하지만 스도쿠에서 활용했던 백트래킹에 익숙하다면 크게 어렵지 않다. 우선 백트래킹의 핵심은 가능여부 return, 다음단계, 마지막단계이다. 우리는 N×N개의 점에 대해 light를 킬지 말지를 결정한다. 처음단계가 0번째 점이라면, 마지막단계는 N×N번째 점이 된다. 즉 입력을 z번째 점으로 한다고 하면, 마지막단계는 z == n×n이 된다. 마지막 단계에서 생각할 것은 이렇게 완성한 n×n개의 지도가 유효한지 하는 것이고, 유효하지 않다면 0을, 유효하다면 전체 지도를 출력한 뒤 1을 return하면 된다. 유효한지 체크하는 것은 여러 방법이 있겠는데, 우.. 2023. 2. 26.

티스토리툴바