백준

1. 문제핵심종말의 날 까지 의 날짜가 몇 번째 날인 지 / 없다면 -1 출력종말의 날는 M과 N의 최소공배수M, N의 범위는 4만 이하이기 때문에 최악의 경우 4만*4만번 째 날이 종말의 날이 될 수 있다.day를 1씩 증가시키면서 확인하면 연산 횟수가 1억번을 초과하기 때문에 시간 제한에 걸려버린다.따라서 조건으로 주어지는 x 혹은 y를 고정값으로 두고 M 또는 N 만큼 day를 증가시켜 일치하는 날이 존재하는 지 확인한다.예를 들어, x를 시작일(=day)로 두고 day += m 씩 날짜를 건너뛰면서 그 날의 y'값이 조건의 y값과 일치하는 지 확인하면 된다. 2. 해결#include using namespace std;int t;int main(){ cin.tie(NULL); ios_b..

1. 문제핵심1번 칸부터 100번 칸까지 도달할 때 주사위를 최소 몇 번 굴려야 하는가1번 칸부터 주사위를 1~6씩 굴렸을 때 도달하는 칸의 cost를 계산해주면서 100번 칸까지 확장해나간다.이 때 x번 칸에 뱀 또는 사다리가 존재하고 이 경우 특정 칸으로 즉시 이동한다.bfs(너비 우선 탐색)으로 탐색하면서 cost를 갱신해 나가고 뱀/사다리가 존재하는 칸은 연결되는 칸에 cost를 계산하도록 한다. 2. 해결#include using namespace std;int n, m;int grid[104];int cost[104];bool visited[104];void bfs(){ queue q; q.push(1); visited[1] = true; while (!q.empty())..

1. 문제핵심100만 길이의 문자열을 한 번만 탐색해서 해결해야 한다.최소 단위인 IOI를 탐색하는 것이 핵심이다. 2. 해결#include using namespace std;int n, m;string input;int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> m >> input; int idx = 0; int cnt = 0; int ans = 0; while (idx IOI가 n만큼 나오면 정답을 1씩 증가하는 로직에서 바로 뒤에 IOI가 추가로 나오는 경우를 고려하지 않아서 틀린 경우가 있었다.IOI가 나온 횟수인 cnt를 0으로 갱신하는 것이 아니라 -1만 해주면 바로 뒤에 I..

1. 문제핵심n개의 회의 일정이 주어진다. (시작시간, 종료시간)회의가 겹치지 않게 일정을 정렬할 때 최대 몇 개 회의일정을 정할 수 있을까일정을 잡는 규칙은 현재 회의 종료 시간 최대한 일정을 많이 잡기 위한 규칙 빨리 시작하고 빨리 끝나는 회의 먼저 일정을 잡는다. 2. 해결#include using namespace std;int n;vector> meetings;bool compare(pair a, pair b){ if (a.second == b.second) return a.first > n; while (n--) { int start, end; cin >> start >> end; meetings.push_back({start,..

1. 문제핵심NxN 맵이 주어지고 1이면 집, 2면 치킨집이다.M개의 치킨집을 고른 경우의 수마다 치킨 거리를 계산한다.그 경우의 수 중에서 최소값을 구한다. 2. 해결#include using namespace std;int N, M, ans = INT32_MAX;vector> house;vector> chicken;void combination(vector> v, int s){ if (v.size() == M) { int dist[104]; fill(&dist[0], &dist[0] + 104, INT32_MAX); for (int i = 0; i > N >> M; for (int i = 1; i > input; if (inpu..

1. 문제핵심최대 100만 개의 수가 주어진다.index 기준으로 오른쪽에 있는 자신보다 큰 수 중 가장 가까운 수를 찾는다.없을 경우, -1을 index 위치에 넣는다.최대 100만 개가 주어지기 때문에 매번 오른쪽 수들을 탐색하는 방법은 안 된다. 2. 해결#include using namespace std;int N;int nums[1000004];int ans[1000004];stack st;int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> N; fill(&ans[0], &ans[N], -1); for (int i = 0; i > nums[i]; while (!st.empty() && n..

1. 문제핵심최대 1만 개의 노드가 주어지고 노드의 관계는 최대 10만 개가 데이터로 주어진다.각 노드와 연결된 노드들을 센 후 최대 개수인 노드를 출력한다.최대 개수인 노드가 여러 개일 경우 오름차순으로 출력한다.시간 제한은 5초모든 연결된 노드의 개수를 셀 경우 최대 1만*1만 = 1억 번 연산을 해야한다.1억 번 이하의 경우 충분히 감당할 수 있는 횟수기 때문에 dfs를 사용한다. 2. 해결#include using namespace std;int N, M;vector arr[10004];int dp[10004];bool visited[10004];int dfs(int x){ int ret = 1; visited[x] = true; if (arr[x].size() == 0) ..

1. 문제핵심-1이 부여된 노드가 최상위 루트노드특정 노드가 제거되었을 때 리프노드의 개수를 구한다.노드간 관계를 인접행렬 또는 인접리스트로 구현한다.제거된 노드로부터 하위노드를 탐색에서 제외하고 리프노드를 탐색한다. 2. 해결#include using namespace std;const int blank = -100;int N, start;vector arr[54];int solve(int idx){ int cnt = 0; stack s; s.push(start); while (!s.empty()) { int now = s.top(); s.pop(); if (now == idx) continue; for (..

1. 문제핵심판의 모서리에는 치즈가 없다.치즈는 한 덩어리가 판에 놓인다.공기에 노출된 치즈는 1시간마다 표면이 녹는다. 치즈 내부의 빈 공간엔 공기가 없다.치즈가 모두 녹는 시간을 잰다.모두 녹기 직전 1시간에 치즈가 놓인 칸의 개수를 잰다.핵심 알고리즘은 dfs나 bfs 탐색으로 단순하지만 문제를 이해하는 능력이 중요하다.치즈의 노출된 부분만 체크하기 위해서 기저조건을 설정하는 것이 중요하다. 2. 해결#include using namespace std;int N, M, cnt, ans1, ans2;int grid[103][103];bool visited[103][103];int dy[4] = {0, 0, 1, -1};int dx[4] = {1, -1, 0, 0};void melt(int y, int..

1. 문제핵심 벽을 3개 설치한 모든 경우의 수를 고려한다. 각각의 경우에 바이러스가 퍼졌을 때 안전영역의 크기를 계산한다.-최대 안전영역의 크기를 갱신한다. 2. 풀이#include using namespace std;int N, M;int mapGrid[10][10];bool visited[10][10];vector> virus;vector> wall;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};void SpreadVirus(int y, int x){ visited[y][x] = true; for (int i = 0; i = M || ny = N) continue; if (visited[ny][nx] || ma..