문제 풀이
-
[백준] 11066번 파일합치기문제 풀이 2020. 8. 6. 19:05
11066 파일 합치기 문제소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, ..
-
[백준] 10830번 행렬 제곱문제 풀이 2020. 8. 5. 19:21
10830번 행렬제곱 문제크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다. 출력첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다. 풀이)B의 범위가 크기 때문에 하나씩 곱해보는 A*A*A..*A 이런식으로 계산하면 시간초과가 나는 문제이다. 지수 법칙을 생각해서 풀어야 하는 문제다. 지수 법칙을 이용해 분할정복(divide and co..
-
[백준] 3197번 백조의 호수문제 풀이 2020. 8. 4. 18:08
3197 백조의 호수 문제두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성한다.입력입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.각 R줄 동안 C만큼의 문자열이 주어진다.'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간..
-
[백준] 2942번 퍼거슨과 사과문제 풀이 2020. 8. 3. 19:16
2942번 퍼거슨과 사과 문제맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하면 경기력 저하가 나타날 수 있으므로 모든 선수에게 같은 개수를 주려고 한다. 퍼거슨 감독은 사과를 싫어한다. 따라서 사과가 남으면 안 된다.예를 들어, 퍼거슨이 빨간 사과를 4개, 초록 사과를 8개 가지고 있다면, 다음과 같이 세가지 방법으로 나누어 줄 수 있다선수 1명에게 빨간 사과 4개와 초록 사과 8개를 줄 수 있다선수 2명에게 빨간 사과 2개와 초록 사과 4개를 각각 줄 수 있다선수 4명에게 빨간 사과 1개와 초록 사과 2개를 각각 줄 수 있다.퍼거슨이 사과를 나누어 주는 방법..
-
[백준] 1202번 보석 도둑문제 풀이 2020. 8. 2. 18:21
1202 보석도둑 문제세계적인 도둑 상덕이는 보석점을 털기로 결심했다.상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)모든 숫자는 양의 정수이다. 출력첫째 줄에 상덕이가 훔칠 수 있..
-
[백준] 10986번 나머지 합문제 풀이 2020. 8. 1. 13:56
10986 나머지 합 문제수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 풀이)update 쿼리가 없고, 구간 합만 구해서 나머지를 확인하면 되는 문제라segment tree 가 아니고 prefix sum 을 이용한 문제다.그리고 모든 ..
-
[백준] 17780번 새로운 게임문제 풀이 2020. 7. 31. 18:31
17780 새로운 게임 문제) https://www.acmicpc.net/problem/17780 풀이)시뮬레이션 문제이다. 선언한 자료들① 말의 정보를 저장하는 구조체를 선언 & 정보 저장 배열 선언struct horse {int y, x, dir; // 말의 위치, 방향 }; vector h_info; ② 체스판의 상태를 나타내는 int map[12][12]; 선언③ 체스판의 위치에서, 가장 아래쪽에 있는 말 번호를 저장하는 int horse_map[12][12]; 선언 만약 (1,1) 자리에 1 - 3 - 4번 순으로 말들이 쌓여있다면horse_map[1][1] = 1이다. ④ 각 말들이 업고? 있는 말 정보 저장하는 vector parent[10]; 선언 만약 1 - 3 - 4 순으로 말들이 쌓여..
-
[백준] 6087번 레이저 통신문제 풀이 2020. 7. 30. 18:42
6087 레이저 통신 문제크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다. 입력첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 10..