15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 예제가 굉장히 많으므로 백준 링크에서 보시길 바랍니다. 50 * 50 보드에서 최대 13개의 치킨집 중 M개를 고르고, 치킨 거리의 최솟값을 계산하면 된다. 13개의 치킨집 중 6개의 치킨집만 남겨야 할 때 최대 경우의 수 13C6 = 1716에, 모든 조합에 대해 거리를 계산하는 6 * 100 개만큼의 데이터만 계산하면 되므로 무조건 1초 안에 해결이 가능하다. 이를 근거로 완전 탐색을 구현했다. 구현 사항 (a, b)의 집과 치킨집 거리 ..

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 3 2 2 2 4 4 4 8 8 8 ans : 16 2048 게임을 5번 진행했을 때 얻을 수 있는 최대 수를 구하면 되는 문제이다. 백트래킹이나 다른 특별한 풀이가 안 떠올라서 먼저 완전탐색으로 가능한지 계산해 보았다. 20*20 크기의 보드에 한 번 이동당 최대 4개의 경우의 수가 있으므로 총 1024개의 보드를 탐색하면 된다. 1024개에 대해 보드를 이동시키는데 N^2 만큼의 시간이 든다고 가정하면 총 시간복잡도는 1024 * ..

18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 예제가 굉장히 많아서 백준에서 보시는 것을 추천합니다. 문제를 요약해 보면서 어떤 기능을 구현해야 할지 생각해 보자. 스티커를 다른 스티커와 겹치지 않게 가장 위쪽 중 왼쪽에 붙인다. 붙일 수 없다면 90, 180, 270도 회전해서 붙여 본다. 그래도 붙일 수 없다면 그 스티커는 버린다. 여기까지 봤을 때 구현사항은 세 가지 정도 보인다. 스티커 붙이기 스티커 회전하기 답 계산하기 스티커를 붙이는 게 가장 중요해 보이는데, 여기서 시간 복잡도가 결정될 것 같다. ..

2차원 배열을 뒤집거나 회전시킬 때 규칙을 외워서 구현하거나 모양에 신경 쓰면서 회전시키면 굉장히 헷갈린다. 간단하게 아래의 방법대로 해보자. 적당히 3*4 정도의 직사각형을 회전시킨다. 단, 회전시킬때 모든 칸에 좌표를 적어놓고 회전시킨다. 회전 후 각 좌표가 어떻게 변했는지 규칙을 찾아본다. 모양에 집중하는 것이 아니라 규칙을 찾는 것에 집중한다. 이제 3*4가 아니라 n*m 직사각형을 회전시키면 어떻게 될지 규칙을 일반화해 보면 끝!

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