boj, 백준) 20058. 마법사 상어와 파이어스톰(C/C++)
1. 문제 링크 www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 2. 문제 개요 크기가 2^N x 2^N인 격자로 나눠진 얼음판이 있다. A[r][c] (행 : r, 열 : c)의 값은 얼음의 양을 나타낸다. 파이어스톰을 시전하려면 시전 할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2^L x 2^L의 크기로 나누고 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸을 기준으로 3개 이상의 얼음과 인접..
boj, 백준) 20057. 마법사 상어와 토네이도 ( C/C++)
1. 문제 링크 www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 2. 문제 개요 토네이도를 크기가 N x N인 격자로 나누어진 모래밭에서 연습하려고 한다. 각 격자에는 모래가 일정량 쌓여있고, 토네이도가 오면 주변으로 흩날리게 된다. 모래밭의 바깥으로 나간 모래의 총량을 구하는 프로그램을 작성하시오. 3. 문제 힌트 (1) 토네이도의 경로 - 1,1 / 2,2 / 3,3/ ... / n-1,n-1,n-1칸 이동하는 것을 볼 수..
boj, 백준) 20056. 마법사 상어와 파이어볼 (C / C++)
1. 문제 링크 www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 2. 문제 개요 마법사 상어가 크기가 N x N인 격자에 파이어볼 M개를 발사한다. 가장 처음 파이어볼은 각자 위치에서 이동을 대기하고있다... 등등 문제가 길고 복잡해서 문제는 다 안다고 가정하겠습니다. 여튼, 마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자. 3. 문제 힌트 (1) 파이어볼을 어떻게 가지고 있을 것인지 생각..
boj, 백준) 5719. 거의 최단 경로( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 2. 문제 개요 주어진 도로의 거의 최단경로를 구하자. 거의 최단경로는 최단경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 3. 문제 힌트 최단경로를 제거해야 하기 때문에, dijkstra 최단경로 알고리즘을 1회 실행하자. 이때, O(n^2)가 아닌 log형태인 우선순위 큐를 사용해야 함. (시간 ..
boj, 백준) 5231. 과외맨 ( C / C++)
1. 문제 링크 www.acmicpc.net/problem/5213 5213번: 과외맨 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른 www.acmicpc.net 2. 문제 개요 위 그림의 가장 왼쪽 위에서 출발하여 가장 오른쪽 밑의 타일까지 이동하는데 최단경로를 구하시오. 가장 오른쪽 밑까지 도달할 수 없으면 타일번호가 가장 큰 곳으로의 경로를 출력. 3. 문제 힌트 BFS로 최단 경로를 구하는 문제, (1) 1개의 타일이 2개의 블록으로 이루어져 있다고 했을 때, 타일의 개수가 가장 적게 ..
boj, 백준) 9177. 단어 섞기 (C / C++)
1. 문제 링크 www.acmicpc.net/problem/9177 9177번: 단어 섞기 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 www.acmicpc.net 2. 문제 개요 세 개의 단어가 주어졌을 때, 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 계산하는 프로그램을 만들어보자. 3. 문제 힌트 완전탐색을 하면 어떻게 될까..? aaab aaac aaabaaac이 입력으로 주어지고, 세 번째 단어인 aaabaaac의 왼쪽 끝에서 오른쪽 끝으로 탐색을 한다고 해보자. 첫 번째 a는 "aaab"의 a인지, "aaac"의 a인지 알..