문제 문제 바로가기> BOJ 10597번: 순열장난 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 풀이 1 ≤ N ≤ 50이므로, 수를 한개 또는 두개 씩 잘라가며, 순열을 만들어 본다! 이 때, 이미 사용한 수, 수열의 범위를 넘어서는 수의 경우는 더 이상 탐색해 볼 필요가 없다. C++ #include #include #define MAX 51 using namespace std; int N, len; vector v; bool isuse[MAX]; void solution(string..

문제 문제 바로가기> BOJ 1655번: 가운데를 말해요 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 2개의 우선순위 큐를 이용하여 문제를 해결할 수 있다. 💡 문제의 핵심은 2개의 우선순위 큐의 차이를 최대 1로 유지하며, 2개의 우선 순위 큐를 1차원적으로 봤을 때, 오름차순 수열이 되도록 만들어주는 것이다! 💡 maxHeap(오름차순)의 top은 항상 minHeap(내림차순)의 top보다 작다. → 오름차순 1. 두 힙의 size의 최대 차이를 1로 만들기 위해서, minHeap..

문제 문제 바로가기> BOJ 9663번: N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 `board[row] = col` 값을 저장하여, 2차원 배열이 아닌 1차원 배열로 문제를 해결할 수 있다. 퀸을 놓을 때 가로, 세로, 대각선을 확인해야 하는데, solution() 함수에서 한 줄에 하나를 놓고, 유망한 경우, 다음 solution을 호출하기 때문에 자동으로 한 row에는 퀸이 하나만 놓인다. 따라서 대각선과 동일한 column에 퀸이 놓여 있는지를 통해 해당 위치가 유망한지 판단해주면 된다. C+..

문제 문제 바로가기> BOJ 2023번: 신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 왼쪽 부터 자리 수를 늘려가면서 소수인지 판정한다. cnt == N , 즉 N 자리가 되기전에, 소수가 아니라고 판별되면, 그 이후로는 더 볼 필요가 없다! 첫 째 자리 수가 소수일 수 있는 경우는 `2, 3, 5, 7` 뿐이고, 둘 째 자리부터 짝수로 끝나는 경우는, 소수가 될 수 없다. 소수를 판별할 때는 N의 제곱근 까지만으로 나누어 보면 된다! 💡 소수 판별 시 N의 제곱근 까지만 나누..

문제 문제 바로가기> BOJ 17472번: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 1. 섬 (2 ≤ 섬의 개수 ≤ 6) 에 대표 번호? 를 매겨주었다. 어떤 섬에서 어떤 섬으로 이어지는 다리인지 알기 위해서! 2. 문제에서 준 조건인, ▷ 다리의 길이 > 2 ▷ 중간에 방향 변화 불가 를 만족 시키는 다리(edge)가 이어주는 섬 두개 (from, to), 다리 길이(len)를 pq에 넣어준다! 이 때, 상 하 좌 우 탐색을 모두 진행하면, 중복되는 edge들..

문제 문제 바로가기> BOJ 17478번: 재귀함수가 뭔가요? 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 풀이 종료 조건과, 규칙을 찾아서 구현해주면 된다 ! C++ #include using namespace std; void recursive(int cnt, int maxcnt){ for(int i=0; i

문제 문제 바로가기> BOJ 17135번: 캐슬 디펜스 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 1. 조합을 구현하여 궁수의 위치를 선정한다. (`solution() 함수`) 2. 정해진 궁수의 위치를 기반으로, 다음을 과정을 반복한다. 궁수의 적 공격 - 공격할 적의 우선순위를 구하기 위해 , pq에서 사용할 ATTACK 구조체 내에서 bool operator를 재정의해주었다. - 모든 궁수는 동시에 공격하므로, 공격 위치를 vector에 넣어두었다가 한 번에 공격해주었다. (이때, 이미 제거한 적을 또 c..

문제 문제 바로가기> BOJ 17070번: 파이프 옮기기1 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 DFS 탐색을 통해 간단하게 해결할 수 있는 문제다! 1. 파이프의 마지막 부분(초기값 : (1,2))을 추적해가면서 DFS 탐색 진행 (가로, 세로, 대각선 이동 방법이 다름) 2. 종료 조건 : 범위를 벗어나는 경우, 빈칸이어야하는 부분인 벽인 경우 (범위를 벗어나는 경우를 확인할 때, N보다 큰지만 확인해주면 된다. 더하는 방향으로만 이동하기 때문!) 3. (N, N)에..

문제 문제 바로가기> BOJ 17406번: 배열 돌리기 4 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 우선 K가 최대 6으로 작기 때문에, 모든 경우의 수를 탐색하는 방법으로 문제를 풀 수 있다. 문제를 풀 때 필요한 점은 다음 2가지 였던 것 같다. 1. 순열을 구현할 수 있는가? 2. 배열을 원하는 대로 조작할 수 있는가? 1(순열 구현) 을 만족하기 위해, cnt 변수와 visited 배열을 활용하여 재귀적으로 호출을 해주었다. 2(배열 조작)은 규칙을 찾는 게 중..

문제 문제 바로가기> BOJ 2206번: 벽 부수고 이동하기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 벽을 하나씩 제거 + BFS 하는 경우, O(N^2*M^2)으로 시간 초과가 발생한다. 생각해보면, 어느 지점(y, x)에 도착할 때, 남은 기회가 있거나 or 없거나 둘 중 하나의 상태로 도착할 것이다. 이 점을 이용해서 BFS 탐색을 진행하면, BFS를 한번만 돌려도 문제를 풀수 있다! 추가로, 가중치가 동일할 때 최단 경로를 찾는 문제이므로, 가장 먼저 (N-1, M..

문제 문제 바로가기> BOJ 15663번: N과 M (9) 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 같은 위치에 같은 수가 오게되면, 중복 수열이 되므로, 이를 방지하기 위해 `prev` 를 이용해서 같은 자리에 같은 수가 오지 못하도록 해주었다! #include #include #define MAX 10 using namespace std; int N, M; bool isused[MAX]; int num[MAX], ans[MAX]; void input() { cin >> N >> M; for (..

문제 문제 바로가기> BOJ 2573번: 빙산 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 dfs를 사용하여 빙하가 분리되었는지 확인해주는 방식으로 문제를 풀었다! #include #include #define MAX 301 using namespace std; int N, M; bool allmelt; int arr[MAX][MAX]; int copy_arr[MAX][MAX]; bool visited[MAX][MAX]; int dy[] = {-1, 1, 0, 0}; int dx[] = {0, ..

문제 문제 바로가기> BOJ 11057번: 오르막 수 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 아래와 같은 규칙을 가지므로, 점화식이 dp[i][j] = (dp[i][j-1] + dp[i-1][j])%DIV 이다! #include #define MAX 1001 #define DIV 10007 using namespace std; int N; int dp[MAX][11]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0)..

문제 문제 바로가기> BOJ 5014번: 스타트링크 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 BFS를 사용해서 푸는 문제였다! #include #include #define MAX 1000001 using namespace std; int F, S, G, U, D; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> F >> S >> G >> U >> D; visited[S] = true; queue q; q.push(..

문제 문제 바로가기> BOJ 1806번: 부분합 1806번: 부분합 첫째 줄에 N (10 ≤ N > N >> S; for(int i=0; i> num[i]; } void solution(){..