목록PS/알고리즘 문제풀이 (157)
득이공간
21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net #include #include using namespace std; char Map[600][600]; queue SearchQueue; int N, M; const int DX[4] = { -1, 0, 1, 0 }; const int DY[4] = { 0, -1, 0, 1 }; int BFS(int StartX, int StartY) { int Count = 0; SearchQueue.emplace(StartX, StartY); while (!Se..
11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net #include #include using namespace std; priority_queue MaxHeap; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; for (int i = 0; i > Input; if (Input == 0) { if (MaxHeap.empty()) {..
17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net #include #include #include using namespace std; int DP[50001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; for (int i = 1; i
11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net #include using namespace std; int DP[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; DP[1] = 1; for (int i = 2; i
9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net #include using namespace std; long long P[101] = { 0, 1, 1, 1, 2, 2, }; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); for (int i = 6; i > T; for (int i = 0; i > N; cout
9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net #include #include #include using namespace std; unordered_map Closet; void TestCase() { Closet.clear(); int N; cin >> N; for (int i = 0; i > First >> Second; ++Closet[Se..
2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net #include using namespace std; int StairScores[301]; int DP[301]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; for (int i = 1; i > StairScores[i]; } DP[1] = StairScores[1]; DP[2] = StairScores[1] + StairScores[2]; DP[3] = m..
14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net #include #include using namespace std; int N, M; int Map[1000][1000]; int Distance[1000][1000]; queue SearchQueue; void BFS(int StartRow, int StartCol) { SearchQueue.emplace(StartRow, StartCol); while (!SearchQueue.empty()) { int CurRow..
1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net #include #include #include using namespace std; int N, R, C; int SearchNum; void DivideSearch(int StartRow, int StartCol, int Size) { if ((R StartRow + Size) || (C StartCol + Size)) { SearchNum += Size * Size; return; }..
2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net #include using namespace std; int Paper[128][128]; int CountWhite; int CountBlue; void DividePaper(int StartRow, int StartCol, int Size) { bool bDivide = false; int ColorCheck = -1; for (int i = StartRow; i < StartRow + Size; ++i) { for (int j =..