문제 문제 바로가기> BOJ 1584번: 게임 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 풀이 BFS 탐색을 진행하되, 안전한 구역인 경우, 그 구역에서 먼저 탐색을 진행해주기 위해 deque 자료구조를 이용했다!! #include #include #define MAX 501 #define DANGER 1 #define DEATH 2 using namespace std; struct DATA { int y, x, lose; }; int N, M; int map[MAX][MAX]; b..

문제 문제 바로가기> BOJ 2636번: 치즈 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 치즈의 구멍인지, 빈칸인지 확이하기 위해서 4꼭지점에서 BFS 탐색을 시작해 주는게 핵심이다! C++ #include #include #define MAX 101 #define EMPTY 0 #define CHEESE 1 using namespace std; struct POS { int r, c; }; int R, C; int total = 0; int map[MAX][MAX]; bool visited[MAX][MAX..

문제 문제 바로가기> BOJ 2842번 : 집배원 한상덕 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 풀이 고도를 ±1 씩 모든 경우의 수를 구할 경우 시간 초과가 발생한다. 50*50*1,000,000 = 2,500,000,000 (25억,,) 하지만 실제 고도의 개수는 50*50 = 2500을 초과할 수 없고, 이를 반영해서 "투 포인터 + 그래프 탐색"으로 풀었다. 1. 투포인터를 이용하기 위해 고도를 정렬해야 한다. 이때, 중복되는 값은 필요 없으므로!! set을 이용해서 중복되는..

문제 문제 바로가기> BOJ 1918번: 후위 표기식 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이 #include #include #include #define MAX 32001 using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); string expr; cin >> expr; stack st; // 우선 순위가 낮은 연산자 (+, -) 부터 큰 연산자 (*, /) 순으로 쌓임 // 연산자 우선 순위 : () > *..

문제 문제 바로가기> BOJ 21758번: 꿀 따기 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 풀이 벌 2마리와 벌통의 위치를 모두 다르게 설정해보는 방식으로 문제를 푼다면 시간 초과가 발생한다. 벌이 2마리, 벌통이 1개이므로, 총 3가지의 경우가 있다. 1. 벌 벌 벌통 이 경우, 첫 번째 벌은 가장 왼쪽에 있는 게 이득이다. 따라서 반복문 O(N)을 통해 두 번째 벌의 위치를 지정해주고, 그 시점에서 얻을 수 있는 이익을 계산한다. 2. 벌 벌통 벌 이 경우, 첫 번째 벌은 가장 왼쪽에, 두 번째 벌은 가장 오른쪽에 있는 게 이득이다. 따라서 반복문 O(N)을 통해 벌통의 위치를 지정해주고, 그 시점에서 얻을 수 있는 이익을 계산한다. 3...

문제 문제 바로가기> BOJ16946번: 벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 매번 벽을 만날 때마다 dfs 혹은 bfs 탐색을 진행하면, 복잡도가 O(N^2*M^2)이고, N과 M 은 최대 1000이므로, 시간초과가 발생한다! 이동 가능한 곳의 영역을 미리 체크해 놓는다면, 시간 복잡도를 O(N^M)으로 줄일 수 있다. 예를 들어 예제 2번의 경우, 4 5 11001 00111 01010 10101 다음과 같이 이동가능한 영역의 size?를 미리 체..

문제 문제 바로가기> BOJ 17471번: 게리맨더링 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 #include #include #define MAX 11 #define INF 100001 using namespace std; int N; int ans = INF; int total = 0; // 총 인구 수 int people[MAX]; // 구역의 인구 수 bool visited[MAX]; // 방문 여부 저장 int isgroup1[MAX]; // 그룹 1에 속하는지 vector v[MAX]; // 각 구역과 인접한..

문제 문제 바로가기> BOJ 2110번: 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 #include #include #define INF 1000000001 #define MAX_HOME 200001 using namespace std; int N, C; int home[MAX_HOME]; void input() { cin >> N >> C; for (int i = 0; i > home[i]; sort(hom..

문제 문제 바로가기> BOJ 2343번: 기타 레슨 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 매개 변수 탐색을 이용해서 가능한 블루레이의 크기 중 최소를 구하는 문제다. 주의할 점은 상한(high)을 설정하는 부분이다. 처음에 high를 10,001으로 설정했는데 바로 틀렸다,, 생각해보니, 각 강의의 길이가 10,000분을 넘지 않는 것이지, 블루레이의의 크기는 당연히 10,000분을 넘을 수 있기 때문!! 이 부분을 주의해 줘야 할 것 같다! 각 강의당 길이가 10,000분이므로, 10000*1000..

문제 문제 바로가기> BOJ 6987번: 월드컵 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 풀이 경기가 진행될 수 있는 모든 경우의 수를 탐색하여, 그 중 하나라도 결과 값과 일치하는 게 있다면 (= 가능한 결과), 1을 출력하도록 풀었다. 모든 경우의 수를 탐색할 경우, 시간 복잡도는 3^15(=14,348,907)(*4 = 57,395,628)로 시간 내 완전탐색이 가능하다! 총 경기 경우의 수는 6C2 = 15 이고, (이 조합을 미리 만들어주는 부분이 make_team() 함수) 두 팀이 경기를 진행..

문제 문제 바로가기> BOJ 16974번: 레벨 햄버거 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, www.acmicpc.net 풀이 패티가 늘어나는 규칙은 " (이전 레벨 패티) * 2 + 1 " 이다. N 0 1 2 3 4 5 ... patty 1 3 7 15 31 63 ... 햄버거의 아래 X장을 먹는 경우에는 총 3가지 경우가 있다. (재귀적으로, 분할정복으로 해결하기 위해) 1. (해당 레벨의) 가운데 패티보다 적게 먹는 경우 : get_patty(n-1, x-1) = 레벨을 낮추어 재귀적으로 탐색해준다. x-1..

문제 문제 바로가기> BOJ 2531번: 회전초밥 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 두 포인터를 조작해가며, 푸는 문제다. 회전 초밥이 "회전하는 벨트 위"에 있음을 주의해야 한다. 따라서 종료 조건이 right == k-1, 즉 회전 초밥 벨트를 모두 확인했을 경우다!!!! C++ #include #define DISH 30001 #define KIND 3001 using namespace std; int N, d, k, c; // 회전 초밥 벨트에..

문제 문제 바로가기> BOJ 11053번: 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP와 이중 for문을 이용해 "현재 수를 마지막으로 하는 가장 긴 증가하는 부분 수열"의 길이를 저장해주었다. 이렇게 저장해두면, 답은 dp 배열 중 가장 큰 값이 되고, 이를 반복문을 돌 때 함께 업데이트 해주면 된다! #include #define MAX 1001 using namespace std; in..

문제 문제 바로가기> BOJ 2098번: 외판원 순회 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 중요한 Point 1. 출발지가 어디든 그 결과는 같다. A → B → C → A B → C → A → B C → A → B → C 조금만 들여다보면, 순회하기 때문에, 어느 지점에서 출발하든 동일한 경로가 되는 것을 확인할 수 있다. 따라서 출발지를 고정 시킨 후 탐색을 진행한다! 2. 중복되는 경로가 생긴다. 이미 방문해서 최소값을 찾아 놓은 부분 경로의 경우, ..

문제 문제 바로가기> BOJ 2042번: 구간 합 구하기 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 indexed tree를 이용해서 푸는 문제다. 다음과 같이 구간합을 저장하고 있는 트리를 만들 것이다. 크게 4가지 단계로 볼 수 있는데, 1. tree의 크기를 설정한다. tree의 크기는 N보다 크면서 N과 가장 가까운 2의 거듭제곱으로 설정하는데, 이는 tree의 depth가 1 증가할수록, 노드의 개수가 2배씩 늘어나는 특징을 반영한..