17070번: 파이프 옮기기 1

17070번: 파이프 옮기기 1사용 언어: C++문제 요약문제 요약이 어려우므로 문제 확인 요망풀이DP로 테이블을 채우면서 파이프를 옮기면 해당 칸 업데이트.dp[r][c][dir]: 파이프 끝이 (r, c)에 있고, dir 방향일 때의 경우의 수. (dir 0 : 가로, 1 : 세로, 2 : 대각선)예를 들어 시작이 (1,1), (1,2)에 파이프가 하나 있으니까 dp[1][2][0] = 1;로 초기화하는 것.또한, 이 문제는 오른쪽과 아래, or 오른쪽-아래로만 움직이니까 dp[1][2]면 자동으로 (1,1)에 다른 쪽 파이프가 있다고 가정 가능.답#include #include using namespace std;int N;int house[17][17];int dp[17][17][3];int ma..

1326번: 폴짝폴짝

1326번: 폴짝폴짝사용 언어: C++문제 요약개구리가 일렬로 놓여 있는 검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오. 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 징검다리..

10830번: 행렬 제곱

10830번: 행렬 제곱사용 언어: C++문제 요약크기가 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제곱한 결과를 출력한다.풀이행렬 제곱을 단순하게 구현하면 A를 B번 곱할 수 있는데 B는 최대 10^11이므로 불가능하다.그래서 분할 정복 거듭제곱을 적용하면 되는데,B가 짝수 지수일 때A^B = (A^(B/2)) ..

11401번: 이항 계수 3

11401번: 이항 계수 3사용 언어: C++문제 요약자연수 N과 정수 K가 주어질 때, 이항 계수 NCK를 1,000,000,007로 나눈 나머지를 구하는 문제입니다.N은 최대 4,000,000까지 주어질 수 있어, 단순 계산으로는 해결이 어렵고1,000,000,007은 소수(prime number)라는 점이 이 문제의 핵심풀이일단 모듈려 연산은 나눗셈에 대해 분배법칙이 성립하지 않고, 계산 자체도 N이 400만까지 가서 단순 계산은 불가능.그래서 해결 방법이 모듈러 곱셈 역원을 쓰는 건데, 이게 어떤 수 B로 나누는 것은, B의 역원(B^-1)을 곱하는 것과 같다는 거고, 이를 이루기 위해 쓰는 것이 페르마의 소정리. 페르마의 소정리페르마의 소정리는, P가 소수이면, a^(P−1) ≡ 1(modP) ..

1717번: 집합의 표현

1717번: 집합의 표현사용 언어: C++문제 요약초기에 0, 1, 2, ..., n의 원소 각각이 자기 자신만 담은 n+1개의 서로 집합으 ㄹ이룬다. 두 연산을 m번 처리한다.1. 합집합 연산 : o a b -> a 가 속한 집합과 b가 속한 집합을 합친다.2. 동일 집합 질의: 1 a b -> a와 b가 ㅈ같은 집합에 속하면 YES, 아니면 No를 출력. 제한은 n 풀이합집합을 하고 해당 두 수가 같은 집합에 있는지 찾는 최적의 방식은 유니온 파인드다.유니온 파인드의 핵심 연산은 두 가지다.1. find(x)- 원소 x가 속한 집합의 대표(root)를 찾는다int find_parent(vector& parent, int x){ if(parent[x] == x) return x; re..

25682번: 체스판 다시 칠하기 2

25682번: 체스판 다시 칠하기 2사용 언어: C++문제 요약N*M 크기의 보드. 각 칸은 'B', 'W'로 칠해짐. 이 보드에서 임의의 K*K 크기 부분을 잘라서 체스판처럼 만들고자 한다. 체스판이란, 흑백이 번갈아 있는 형태이며 왼쪽 위 칸이 흰색인 경우와 검은색인 경우 두 가지가 존재한다. 목표는, K*K 크기의 구간을 선택한 뒤, 체스판으로 만들기 위해 다시 칠해야 하는 정사각형의 최소 개수를 구하는 것이다.풀이1. 두 체스판 패턴과 비교- 입력 보드와 두 체스판 패턴(W 시작, B 시작)을 비교하여 틀린 칸 수를 0과 1로 기록.- 이를 통해 diff_w[i][j], diff_b[i][j] 배열을 만듦 2. 2차원 누적합(prefix sum) 계산- 각 diff 배열에 대해 2차원 누적합을 만..

10986번: 나머지 합

10986번: 나머지 합사용 언어: C++문제 요약수 N개 A1, A2, ..., AN이 주어진다. 이때 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.풀이처음에는 아래와 같이 모든 (i, j) 쌍에 대해 부분합을 구하고,그 값이 M으로 나누어떨어지는지 검사하려 했지만 시간 초과가 났다.for (int i = 1; i 그래서 시간을 어떻게 줄일 수 있을까 고민해봤는데, 위의 O(N^2)이 아닌 O(N)으로 줄일 수 있었다.방법은 누적합 + 나머지 활용이다. 누적합을 다 하고, 나머지가 같은 prefix 값들끼리 nC2 로 조합하는 것이다.예를 들어 나머지가 1인 prefix 수가 4개면, 이 4개 중 2개 씩 고르면 prefix[4] - prefix[2]를 하..

12865번: 평범한 배낭

12865번: 평범한 배낭사용 언어: C++문제 요약한 달 후 군대에 가는 준서는 여행을 떠나기 전 최대한 즐거운 추억을 만들기 위해, 배낭에 넣을 수 있는 물건의 가치 합의 최댓값을 고민하고 있다.준서는 N개의 물건을 가지고 있고, 각 물건은 무게 W와 가치 V를 갖는다.배낭에 넣을 수 있는 최대 무게는 K일 때, 배낭에 담을 수 있는 물건들의 가치의 최댓값을 구하라.단, 각 물건은 한 번씩만 사용할 수 있다.풀이이 문제는 전형적인 0-1 배낭 문제로, 동적 계획법(DP)을 이용해 푸는 문제다.dp[j]: 최대 무게가 j일 때의 최대 가치각 물건을 한 번씩만 사용할 수 있으므로, 무게 j부터 역순으로 갱신해야 한다.#include #include using namespace std;int main(){..