문제 문제 바로가기> 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..

문제 문제 바로가기> SWEA 5650번: 핀볼 게임 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 크게 3가지를 고려해주었다. 1. simulation 시, 빈칸의 좌표만 따로 담아 둘 것인지? 그냥 2중 for문을 돌면서 빈칸을 찾을 것인가? 빈칸의 좌표를 따로 담아둘 경우, 저장 공간은 더 사용하지만, 조금 더 속도를 높일 수 있을 것 같다는 생각이 들었지만, 빈칸이 많은 경우, 저장 공간 + 속도 측면에서 모두 별로라고 판단해서 100*100이기 때문에 그냥 2중 for문을 도는 것을 선택했다. 2. 웜홀을 어떻게 쌍을 지어줄 것인지 웜홀이 2개가 쌍으로 들어오기 때문에, vector의 pair..

문제 문제 바로가기> 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 23291번: 어항 정리 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 어항을 쌓는 부분을 제외한 나머지 부분의 구현은 평이한 편이다.. 다만 어항 쌓느라 1시간 넘게 쓴 것 같다 ... 어항 쌓기 규칙을 찾아주는 게 어려웠다 ... 조금 .... 많이 ... 💡 어항 쌓기 규칙 총 5가지 변수를 이용해서 규칙을 찾았다. cnt : 그냥 1, 2, 3, 4, ... monotonic 하게 증가 idx : cnt가 짝수인 경우 1 증가한다. pivot이 증가할 때 pivot+=..

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

문제 문제 바로가기> BOJ 23289번: 온풍기 안녕! 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 풀이 벽을 고려해야해서,, 온풍기에서 바람이 나오는 부분을 구현하는 게 힘들었다 ,, 다음과 같은 규칙성을 가진다!! 규칙성이 필요한 BFS 였다,, ("같은 온풍기에서 나온 바람이 여러 번 도착"해도 온도를 여러번 상승시키지 않기 위해 visited 배열을 이용해주었다.) 벽은 4차원 배열을 이용해서 그 정보를 저장해주었다!! (코드 input 함수 참조) 비록 시간은 엄청 오래 걸렸지만 .... 2~3시..

문제 문제 바로가기> BOJ 2458번: 키 순서 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이 인접 리스트를 이용하여 간접적으로 대소 비교가 가능한지 확인해 주었다! import java.io.*; import java.util.*; public class Main { static int N, M; static boolean[][] check; static List[] small, big; private static int solution() { ArrayDeque q = new ArrayDeque()..

문제 문제 바로가기> BOJ 6087번: 레이저 통신 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 풀이 한 단계 더 발전한 BFS 느낌이었다. 핵심은 4차원 방문 배열 + Prioirty Queue 이용이다. 💡 최단 거리가 아닌, 최소로 거울을 활용하는 횟수를 구하므로, Priority Queue를 이용하여 가장 적은 거울이 필요한 경우부터 탐색해주었다. 💡 visited[y][x][before_dir][next_dir] : 위치 (y, x) , 이전 방향 before_dir , 다음 방향 ne..

문제 문제 바로가기> SWEA 2382번: 미생물 격리 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 .... 정말... 국어를 잘해야한다. 주의할 점 1. 군집이 동시에 움직인다. 처음에 번호순서대로 움직여서 답이 이상하게 나왔다 ^^,, 이를 위해 tmpMap 배열을 이용해주었다! 2. "이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다." 이 부분에서 구현 실수가 있었다. 예를 들어 군집 A=3, B=4, C=5라고 해보자. A, B, C 순서로 동일 칸에 도착했을 때, C의 방향이 해당 군집의 방향이 되어야 한다. 그런데 만약 A < B 이니까, B의 크기를 7 로 저장을..

문제 문제 바로가기> SWEA 2112번: 보호 필름 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 "성능검사를 통과하기 위한 최소 약품투입 횟수"를 구하기 위해 부분 집합을 이용해 문제를 풀었다! #include #define MAX_Y 14 #define MAX_X 21 using namespace std; int Y, X, K; int ans = 0; bool film[MAX_Y][MAX_X]; void input() { cin >> Y >> X >> K; for (int i = 0; i > film[i][j]; } a..

문제 문제 바로가기> SWEA 4193번: 수영대회 결승전 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 우승 경로 (= 가장 빠른 시간 내 도착점) 에 도착해야하므로, BFS를 이용했다! 소용돌이는 2초동안 유지되다가 1초동안 잠잠해지므로, 현재시간 % 3 == 2 인 경우가 소용돌이가 잠잠해지는 경우이다! 소용돌이가 잠잠해지지 않은 경우에는 현재 위치에서 대기해야하므로, 초를 + 1 한 후, 현재 정보를 다시 queue에 넣어 주었다! #include #include #include #define MAX 16 #define EMPTY 0 #define WALL 1 // 섬과 같은 장애물 #define..

문제 문제 바로가기> BOJ 16434번: 드래곤 앤 던전 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 풀이 이분 탐색을 이용해, "용사가 N번째 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를"를 구해주었다. HMaxHP의 범위는 int 범위를 넘어갈 수 있기 때문에, long long 으로 설정해주어야 하며, 용사와 몬스터의 전투 과정 또한 반복문을 통해 일일이 해보는 것이 아닌, 수식 계산을 통해 해주어야 한다! ( ex 용사의..