문제 문제 바로가기> BOJ 9935번: 문자열 폭발 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 풀이 문자열을 폭발시킬 때는 LIFO, 남은 문자열을 합칠때는 FIFO 자료구조가 용이하기에 deque를 사용했다. 문자열 폭발시 LIFO 자료구조를 이용하여 시간을 단축시킬 수 있는데, 그 이유는 가장 최신 폭발 문자열 개수만 보고 판단할 수 있고, stack 덕분에 문자열의 순서가 유지되기 때문이다. ( + stack 같은 자료구조의 유용성을 알 수 있는 좋은 문제같아서, 한번 풀어보면 좋을..

문제 문제 바로가기> BOJ 2666번: 벽장문의 이동 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 풀이 처음에는 3가지 케이스 별로 나누어서 풀었는데, right 보다 작은 경우는 left 문을 이용하고, left보다 작은 경우는 right 문을 이용하도록 하면 두개의 if문으로 코드를 줄일 수 있었다..! 밑에 그림을 참고하자 :) + 추가로 left와 right를 파라미터로 가지고 다니면, 원상태로 복원시켜줄 필요가 없어서 변수관리가 편리하다! #include #define MAX 25 using..

문제 문제 바로가기> BOJ 10157번: 자리배정 10157번: 자리배정 첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. www.acmicpc.net 풀이 달팽이 모양을 그릴 수록 R, C 칸이 한칸씩 감소하는 성질을 이용하여 문제를 해결했다! #include #include #define pii pair using namespace std; int C, R, K; int dr[] = {1, 0, -1, 0}; // 상 우 하 좌 int dc[] = {0, 1, 0, -1}; void input(){ cin >> C >> ..

문제 문제 바로가기> BOJ 8983번: 사냥꾼 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 풀이 중요한 포인트는 "사대를 기준으로 동물을 보는 것"이 아니라, "동물을 기준으로 사대를 보는 것"이다. 사대를 정렬해두고, 해당 동물을 잡을 수 있는 사대가 있는지 이분탐색을 이용하여 확인하면, MlogM(사대 정렬) + NlogN(나를 잡을 수 있는 사대 찾기) → O(MlogM) 만에 문제를 해결할 수 있다. #include #include #def..

문제 문제 바로가기> BOJ 1079번: 쇠막대기 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 풀이 닫는 괄호 ')' 일 경우 두 가지 경우가 있다. 1. 쇠막대기의 끝인 경우: 자신(조각)을 정답에 더해준다 (+1) 2. 레이저의 끝인 경우 = 이전 문자가 '(': 이때까지 쌓인 쇠막대기 개수만큼 정답에 더해준다 (+siz) #include using namespace std; string str; void input(){ cin >> str; } void solution(){ int ans=0, siz=0; for..

문제 문제 바로가기> BOJ 9047번: 6174 9047번: 6174 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스마다 한 줄에 네 자리 수(1000~9999)가 하나씩 주어진다. 단, www.acmicpc.net 풀이 1 타입을 문자열과 정수로 변환해가며 풀었다! 이때 정수 -> 문자열로 변환하는 과정에서 0089 같은 것이 나올 수 있으므로 자리 수를 맞춰주는 연산을 추가로 진행해주었다. 이런 과정을 거치지 않으려면, 풀이2와 같은 방법으로 풀 수도 있다. #include #include #include #include #define SIZE 4 using namespace std; in..

문제 문제 바로가기> BOJ 2304번: 창고 다각형 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 풀이 L이 최대 1000이므로, brute-force 방식으로 문제를 쉽게 해결할 수 있다 ! #include #include #define MAX 1001 using namespace std; int N, L, H; int pillars[MAX]; int maxVal, maxIdx; void input(){ cin >> N; for (int i = 0; i > L..

문제 문제 바로가기> BOJ 17485번: 진우의 달 여행 (Large) 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 풀이 "달 여행에 필요한 최소 연료의 값"을 구하기 위해 모든 경우의 수를 따져보는 경우 O(N^3)이므로, 보자마자 DP로 풀어야 할 거 같은 느낌이 들었다! 나는 우선 각 방향에 번호를 붙여주었다. (k : 0 ~ 2) 다음으로 dp 배열의 의미를 다음과 같이 정의해 주었다. dp[y][x][k] : dp[y][x][k] : 방법 k로 (y, x)에..

문제 문제 바로가기> BOJ 2230번: 수 고르기 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 정렬과 투 포인터를 이용하여 O(nlogn) 안에 문제를 해결할 수 있다. #include #include #define MAX 100001 using namespace std; int N, M; int num[MAX]; void input() { cin >> N >> M; for (int i = 0; i > num[i]; } void solution() { ..

문제 문제 바로가기> BOJ 16928번: 뱀과 사다리 게임 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이 사다리와 뱀 정보를 path 배열에 저장해주고, BFS를 통해 문제를 해결할 수 있다. BFS를 진행하는 이유는 "100번 칸에 도착하기 위해 주사위를 굴려야하는 횟수의 최솟값"을 구해야하기 때문이다. #include #include #define MAX 101 using namespace std; int N, M; int path[MAX]; bool ..

문제 문제 바로가기 > BOJ 1347번: 미로 만들기 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 풀이 미로의 어느 지점에서 이동을 시작할지 모르기 때문에 maze 크기를 101로 잡아주었다. 시뮬레이션을 통해 방문한 곳은 true로 변경해주고, 이후 boundary를 찾아 미로를 출력해준다! #include #define MAX 101 using namespace std; struct HJ {int y=50, x=50, d=2;} hj; // 홍준 int moveCnt; string content; ..

문제 문제 바로가기> BOJ 9207번: 페그 솔리테어 9207번: 페그 솔리테어 각 테스트 케이스에 대해서, 핀을 움직여서 남길 수 있는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 출력한다. www.acmicpc.net 풀이 문제가 잘 이해되지 않았다,, 푸는 것보다 이해하는 데 오래 걸렸다 ,, 테스트 케이스 1번에 대해 다음과 같이 핀이 3번 이동하는 것이다!! ###...### ..oo..... .....oo.. ......... ###...### ###...### ....o.... ....o.... ......... ###...### ###...### ....o.... ......... ......... ###...### #include #define R 5 #define..

문제 문제 바로가기> BOJ 11438번: LCA 2 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 N이 최대 100,000이고, M 또한 최대 100,000이므로 두 노드의 공통조상을 찾기 위해 하나씩 올라가면서 비교하다보면, O(NM)으로 시간초과가 발생한다. 따라서, 두 노드의 공통조상을 찾을 때, 조금 더 빠르게 찾아줄 수 있어야 하는데, 이를 위해 2^k 번째 조상까지 저장하는 ancestor 배열을 만들어주었다!! ex ) ancestor[8][22] : 22번 노드의 2^8번째 조상..

문제 문제 바로가기> BOJ 1799번: 비숍 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 풀이 문제의 핵심은 "비숍의 이동 방식(체스판의 색깔)" 이다. 비숍은 대각선으로만 이동 가능하고, 이는 이동 전과 이동 후의 체스판의 색깔이 같음을 의미한다. 이 부분이 왜 핵심인가!! 그 이유는, 같은 색깔에 있는 비숍끼리만 영향을 끼칠 가능성이 있기 때문!! 이다. 따라서 전체 경우의 수인 2^(N*N)을 한번에 모두 탐색하는 것이 아닌, 검은색, 흰색으로 나누어 2번 탐색 + backtracking 하여, 2(검은색,..

문제 문제 바로가기> BOJ 3055번: 탈출 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 BFS를 이용하여 문제를 해결했다. 물이 매 분마다 비어있는 칸으로 확장하고, 다음 시간에 물이 찰 예정인 칸으로 고슴도치가 이동할 수 없으므로 고슴도치의 이동 전에, 물의 확장을 먼저 처리해주었다. (분이 바뀔 때 마다 처리해주기 위해서 now 변수를 이용) import java.io.*; import java.util.*; public class Main { static final int[] dy = {-1, 1, 0,..