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

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

문제 문제 바로가기> BOJ 16987번: 계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 브루트포스 방식으로 가능한 모든 경우를 탐색해서 "인범이가 깰 수 있는 계란의 최대 개수"를 구해주었다! import java.io.*; import java.util.*; public class Main { static int N, ans; static int[][] egg; public static void main(String[] args) throws Exception { Bu..

문제 문제 바로가기> BOJ 1194번: 달이 차오른다, 가자. 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 미로를 탈출하는데 드는 이동 횟수의 최솟값을 찾는 것이므로, BFS 키를 가진 상태(2^6 경우 존재)에서의 방문 여부를 체크해줘야 하므로, 비트마스킹을 이용했다. import java.io.*; import java.util.*; public class Main { static final int[] dy = {-1,1,0,0}; static final int[]..

문제 문제 바로가기> BOJ 17836번: 공주님을 구해라! 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 한 칸을 이동하는데, 1 시간이라는 동일한 가중치가 필요하고, 최단 시간을 찾는 문제이기 때문에 BFS 탐색을 이용한다! 이 때 그람을 획득한 경우와 아직 그람을 획득하지 못한 경우가 있으므로 두 가지 경우에 대해 체크해주기 위해 3차원 cost 배열에 값을 저장해준다. cost[y][x][0] : (y,x)에 도착하는 데 걸린 시간, 그람을 획득하지 못한 상태 cost[y][x][..

문제 문제 바로가기> BOJ 1600번: 말이 되고픈 원숭이 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 bfs + 3차원 배열을 이용해서 풀었다. visitCnt[y][x][k] : 말처럼 이동할 수 있는 기회가 k번 남았을 때, (y, x) 에 도달하는 최소 횟수 import java.io.*; import java.util.*; public class Main { static final int dy[] = {-1, 1, 0, 0, -2, -2, -1, -1, 1, 1, 2, 2}..

문제 문제 바로가기> BOJ 16724번: 피리 부는 사나이 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이 dfs 탐색을 통해 이동을 진행하다가, 해당 턴에서 이미 방문했던 곳으로 돌아오는 경우, SAFE ZONE이 필요한 것이므로 ans를 1증가해주었다! #include #include #define MAX 1001 using namespace std; int N, M, ans=0; char map[MAX][MAX]; int visited[MAX][MAX]; void..

문제 문제 바로가기> BOJ 2193번: 이친수 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 dp[N][0] : N자리 수 이찬 수 중 0으로 끝나는 수 dp[N][1] : N자리 수 이찬 수 중 1로 끝나는 수 0으로 끝나는 수는 0과 1이 뒤에 붙을 수 있다. 1로 끝나는 수는 0이 뒤에 붙을 수 있다. 이 점을 이용해서 dp로 문제를 해결했다! #include #define MAX 91 using namespace std; long long dp[MAX][2]; int main() {..

문제 문제 바로가기> BOJ 17404번: RGB거리 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 BOJ 1149번: RGB거리 에 1번집과 N번 집이 연결되어 있다는 조건이 조금 더 붙었다. 따라서 1번 집의 색상을 고정하고, 나머지 집들을 칠하는 방식으로 문제를 해결했다. 1번 집의 색상을 고정한 이유는 마지막 N번 집을 같은 색상으로 칠해주지 않기 위해서다!! (조건문을 통해 처리) #include #define MAX 1002 using namespace std; i..

문제 문제 바로가기> BOJ 1766번: 문제집 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 세가지 조건에 따라 문제를 풀 순서를 출력해야한다. 1. N개의 문제는 모두 풀어야 한다. ⇒ 항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다고 했으니, 신경 쓸 필요 없다. 2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. ⇒ 위상 정렬을 이용해서, 정해진 순서를 만족시키도록 한다. 3. 가능하면 쉬운 문제부터 풀어야..

문제 문제 바로가기> BOJ 1726번: 로봇 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 풀이 BFS + Priority Queue를 이용해서 문제를 해결했다. 문제 해결에 있어 중요한 점을 몇가지 적어보겠다! 1. 로봇이 어떤 좌표(y, x)에서 방향 d를 바라보고 있는 경우는 유일하다. 즉, 한번만 처리해주고, 다시 처리해줄 필요가 없다. 어떻게 왔든, 그 이후로 펼쳐질 결과는 동일할 것이기 때문! 이를 위해 3차원 visited 배열을 이용해주었다. 즉, visited[y][x][로봇이 바라보고 있는 방향]이..

문제 문제 바로가기> BOJ 23309번: 철도 공사 23309번: 철도 공사 첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 $N$과 공사 횟수를 나타내는 양의 정수 $M$이 주어진다. ($1 \le N \le 500\,000$, $1 \le M \le 1\,500\,000$) 두 번째 줄에는 공사 www.acmicpc.net 풀이 이중 연결 리스트 개념을 이용하되, 각 원소에 접근할 때 O(1)로 접근하기 위해 이전 역(prev)과 다음 역(next)을 가지는 벡터를 만들어 주었다. 그렇지 않고, 해당 역을 찾기 위해 또다시 탐색을 진행해야 한다면, 시간 초과가 발생하기 때문!! O(N*M),,, #include #include #define MAX 1000001 using..

문제 문제 바로가기> BOJ 12852번: 1로 만들기 2 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 처음엔, 아래와 같이 dp 배열을 구축한 후, 구축된 배열에서 역추적해가며 N을 1로 만드는 방법에 포함되어 있는 수를 출력해주었다. 이 때는 ,, dp[1] = 0을 1로 초기화 해줘서 앞에서 리턴하게 하고 암튼 그랬지만, 전반적인 역추적 아이디어는 아래와 같았다. 그런데 사실 dp 배열을 만드는 과정에서 배열을 하나 더 만들어서 그 이전 값을 저장하는 dp 배열을 만든다면??!! 더 편하게 "N을 1로 만드는 방법에 포함되어 있는 수"를 구할 수 있다!! dp 배열이 업데이트 됨에 따라 그 값을 담고 ..

문제문제 바로가기> BOJ 2623번: 음악프로그램 2623번: 음악프로그램첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이보조 PD들이 정해 놓은 순서를 모두 만족 시키는 최종 순서를 찾아야 하기 때문에 위상정렬을 이용해서 문제를 풀었다! 주의 할 점은 이미 들어온 순서 쌍이 또 들어올 수 있다는 점이다. 이를 중복 처리 해주지 않기 위해 set을 이용했다! #include #include #include #define MAX 1001 using namespace std; int N, M; int inDegr..