https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 1. Logic 해당 문제의 조건을 보면 사무실의 범위가 최대 8 * 8로 아주 작은것을 알 수 있다. 그렇기 때문에 완전탐색으로 구현할 수 있다. 시간복잡도는 모든 사무실을 다 탐색할 경우 8 * 8, CCTV의 4방향을 다 탐색한다는 가정 하 최악의 경우 8 * 8 * 4 정도가 나올 것 같다. 먼저 각 cctv 타입 별 탐색할 수 있는 범위의 경우의 수는 1번 CCTV : 상, 하..
완전탐색
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. Logic - 먼저 시간 복잡도를 계산해봤을때 넉넉잡아 계산해도 50 * 50 * 13 * 13을 해도 42만정도가 나오기 때문에 충분히 돌 수 있다. 그러므로 완전탐색 문제인 것을 알 수 있다. 폐업시키지 않을 치킨집의 최대 갯수를 준다고 했는데 치킨집은 많으면 많을 수록 좋기 때문에 다 골라준다고 생각하면 된다. 여기서 폐업시킨다는 뜻은 고르지 않는다로 생각하고 치킨..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 1. Logic - 기본 BFS의 형식을 지켜 돌지만 for문을 돌게 되면 원하는 자리가 아닌 제일 처음 나오는 인덱스부터 돌기 때문에 완전탐색을 통해 Land의 모든 부분에서 돌아본 후 가장 최대값을 출력하면 된다. - 모든 인덱스에서 다 돌아봤을때 최대 시간 복잡도는 50 * 50 * 50 * 50 이 되므로 최대 6,250,000이 되어 1억을 넘지 않음으로 풀이 가능하다. 2. Code #in..
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 1. Logic 1. 인접한 두 칸에 있는 사탕을 서로 바꿔야하기 때문에 swap함수를 사용해서 값을 변경해 준다. 2. 같은 색의 사탕을 먹어야 하기 때문에 현재칸과 그 다음칸을 비교하면서 진행하며 cnt를 올려준다. 3. 최댓값을 갱신해준다. 2. Code #include using namespace std; vector vec; int n; int calc() { // 가로 int ans = -92735; for(int i = 0; i < n; i++) { int cnt = 1; for(int j = 0; j..
https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 1. Logic 2가지 상황으로 분할해 볼 수 있다. 1. n이 99이하인 경우 2. n이 100이상인 경우 - 1 ~ 99까지의 수는 항상 등차수열을 이루기 때문에 99이하의 숫자가 나오게되면 즉시 숫자를 리턴한다! - 100이상의 숫자는 어짜피 999까지 비교하면 되기 때문에 3부분으로 나눠서 100자리 10자리 1자리 숫자를 각각 비교한다. 2. Code #include using namespa..
https://www.acmicpc.net/problem/10448] 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 1. Logic - 세 합이 100을 넘는 경우는 n이 45인경우부터 1000을 넘기 때문에 45까지 for문을 돌며 합을 계산해 놓는다. - 계산하고 싶은 삼각수를 받은 후 3중 for문을 돌며 찾게되면 값을 반환한다 2. Code #include using namespace std; int triangleNum[1001]; bool FindTri(int n) { for(int i =..
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 1. Logic 1. 난쟁이들의 키의 총 합이 100이고 난쟁이들의 수가 정해져있기 때문에 키를 입력받으면서 동시에 전부 더해준다 2. 2명을 제외하면 되기 때문에 2중 for문을 돌면서 2명의 키를 뺀것이 100이 되면 출력해준다. 2. Code #include using namespace std; vector vec; int main() { int sum = 0; for(int i = 0; i < 9;..
