노는 게 제일 좋아

간단한 산수문제다. 메모리제한 256이 아니라 512네? 우선 두고보자 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 시간 5분이나 더 썼다. 1,000,000 * 1,000,000 는... 우선 21억을 넘어간다. ㅎㅎ int형으로는 불가능 long long으로 쓰자. 64비트다. int는 32 비트다. 2^32배 더 큰 수를 표현할 수 있다. 21억 * 21억 하면 되겠다. # 맞는..

구현하라는 대로 그냥 구현만 해주는 문제다. 메모리가 아주 적다. https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 문제 범위가 0부터면 쉽겠는데..? 역시 문제를 어렵게 하려면 입력을 드럽게 주면 된다. 하지만 우리가 중요한 것은 연도다. 연도는 해가 한 바퀴 도는 것이 중요하지 연도가 중요하진 않다. 다같이 -1을 해주자 # 맞는 풀이 #include using namespace std; int main(){ int E,S,M; int e,s,m;..

// 2022.02.27 다시 품 어려운 문제는 아닌데.. 정확하게 시키는대로 하는 것이 어렵다. 아니.. 하는 것이 어려운 것보다 우리가 짜는 알고리즘이 어떻게 진행될 지 정확하게 알아야 한다는 것이 포인트다. https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 큐를 이용하는 것 같지만. 여기서 중요한 조건이 뒤에 문서를 확인해야한다는 말이 있다. 즉, 탐색이 가능해야한다는 것이다. 스택, 큐는 전체 탐색이 불가능하다. 그렇게 만들어졌다. 때문에 전..

이 문제도 BFS의 기본적인 문제라고 볼 수 있지만 역시나 BFS를 어렵게 하려면 입력을 이상하게 주면 된다. https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이번 풀이의 핵심은 BFS가 아니다. 문제에서 이 사각형의 넓이를 무엇으로 구할 것이냐? 가 문제다. 또한 주어진 조건에 대해서 어떻게 예외처리를 할 것이냐? 가 문제다. 우리가 지금 노드의 개수와 사각형의 개수가 1:1 대응하는가? 꼭짓점이 노드라고 한다면 8 * 6..

뭐 이것도 BFS의 기본문제라고 볼 수 있겠다 다만 이건 입력을 특이하게 받는 케이스? 라고 보면 된다. https://www.acmicpc.net/problem/1012 #맞는 풀이 하지만 정제되지 않음 손에 익지 않아서 20분정도 걸림 주석포함 솔직히 다른 사람은 어떻게 그렇게 정제된 풀이가 바로 생각나는거지??... 아직 갈 길이 멀다. #include #include #include #define X first #define Y second using namespace std; int tc; int dx[4] = { -1,0,1,0 }; int dy[4] = { 0,1,0,-1 }; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> tc; //t..

BFS의 응용문제로 BFS라고 생각지 않지만 의외로 BFS라서 놀라는 초보인 나에게는 놀라움의 대상이었던 문제다. https://www.acmicpc.net/problem/1697 이 문제도 내가 풀긴 풀었지만 왠지 더 잘 풀수 있을 것 같다. #1 뭔가 틀린 풀이 #include #include #include using namespace std; int dist[100001]; // 0 m >> n; queue Q; fill(dist, dist+100000, -1); // 0~ 100000까지 -1 dist[m] = 0; Q.push(m); while(!Q.empty()){ int cur = Q.front(); Q.pop(); if(cur-1 >= 0 && dist[cur-1] < 0){ dist[c..

BFS의 응용문제다. 어렵진 않지만 응용하는 첫번째 단계라고 할 수 있다. www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제도 BFS를 이용한다는 감이 온다. 고려해야 할 조건이 몇가지 있다. 1. 지훈이의 탈출 조건 2. 불이 있는 곳에 지훈이 있을 수 없다. 우선 지훈이는 문제에서 가장자리에 있으면 탈출 할 수 있다. 즉, [ i ][ j ] 위치에서 i 또는 j 가 0을 가지거나 최댓값을 가지면 탈출한 것이다. -> 다시 말해서 가..

이것도 BFS의 기본이라고 볼 수 있다. www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이전 문제의 최단경로의 경로문제라고 해도 무방하다. 하지만 약간 꼬아놨으니 BFS의 시작점이 여러군데다. 근데 뭐 별다를 거 없다. 시작점을 큐에 다 넣고 시작하는 것과 같이 얘도 똑같이 해주면 된다. #맞는 풀이 다만 최적화는 되어있지 않은 풀이 #include #include #define X first #define Y second using nam..

이 문제도 이전 문제와 형제문제라고 할 정도로 BFS의 기본을 알려준다 [프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 2178번 C++ [CPP] www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 바로 이 문제가 BFS가 탐색한 노드의 수를 알려주는 것인데 뭐 메모리랑 관련이 있다고만 해두겠다. **사실 큐에 쌓이는 노드가 더 메모리랑 관련있지만..뭐 그렇다. # 맞는 풀이 #include #include using n..

경로 탐색의 핵심은 탐색 방법이다. 그 중 얘는 BFS다. www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 왜 BFS일까?는 최단경로를 찾아야하기 때문이다. DFS는 최단경로를 보장하는 방법이 아니다. 어떠한 경우에 대해서도 최단경로를 찾기 위해서는 BFS를 쓸 수 있다. 일반적으로 메모리는 DFS보다 BFS가 많이 먹을 수 있는..가능성이 높다 나는 이것을 논리가 맞다고 생각하고도 엄청 많이 틀렸다. 바로 입력에 대해서 확인을 소홀히 해서 그렇다. 이 문제에서 입력은 공백없이 주어졌다. ..