문제링크 : https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; const int MOD = 1000000007; ll func(ll a, ll b) //분할 거듭제곱 { ll tmp = 1; while(b) { if(b%2) tmp = tmp * a % MOD; //홀수 a = a * a % MOD..
문제링크 : https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; const int MOD = 1000000007; int M, N, S; ll func(ll a, ll b) //분할 거듭제곱 { ll tmp = 1; while(b) { if(b%2) tmp = tmp * a % MOD; //홀수 a = a * a % MOD; //..
문제링크 : https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[1001]; int dp_plus[1001]; int dp_minus[1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; for(..
문제링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, result = 0; int arr[8][8]; //원본 int arr2[8][8]; //감염 int wall[8][8]; //벽 int dx[] = {1, -1, 0 , 0}; int dy[] = {0, 0..
문제링크 : https://www.acmicpc.net/problem/28293 28293번: 자릿수 첫째 줄에 정수 $a$, $b$가 공백으로 구분되어 주어진다. $(1 \le a \le 10\,000; 1 \le b \le 10\,000\,000)$ $a^b$의 자릿수가 $10\,000$ 또는 $9,999$로 시작하지 않는 입력만 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int a, b; cin >> a >> b; ll result =..
문제링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; vector house; //집 vector chicken; //전체 치킨 집 vector choice; //선택한 치킨 집 int arr[51][51]; bool visited[14]; in..
문제링크 : https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; typedef vector matrix; ll N, B; matrix multiply(matrix &a, matrix &b) { matrix temp(N, vector(N)); for(int i=0; i> B; matrix ar..
문제링크 : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M; int arr[1001][1001]; bool visited[1001][1001][2]; //0 : 벽 안부숨, 1 : 벽 부숨 int dx[] = {1, -1, 0, 0..
문제링크 : https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; typedef vectormatrix; const int MAX = 987654321; const int MOD = 1000000007; matrix multiply (matrix&a, matrix&b) { matrix tmp(2, vector(2)); for(int i=0; i I * A1 : result(A1) A1 * A1 : A2 ..
문제링크 : https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, R, result; vectorv[101]; int arr[101]; int dist[101]; priority_queue pq; void dijkstra(int s) { for(int i=0; i> ..
문제링크 : https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; char arr[3072][6143]; //세로 N, 가로 2N-1 void draw(int y, int x, int n) { if(n==3) //반복되는 기본 형태 그리기 { arr[y][x] = '*'; //첫째줄 arr[y+1][x-1] = '*'; //둘째줄 ..
문제링크 : https://www.acmicpc.net/problem/28279 28279번: 덱 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; dequedq; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; while(N--) { int num, x; cin >> num; switch(num) { cas..
문제링크 : https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; vectorvec[100001]; bool visited[100001]; int result, target; void dfs(int idx, int dist) { visited[idx] = 1; i..
문제링크 : https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; vectorvec[100001]; bool visited[100001]; int result, target; void dfs(int idx, int dist) { visited[idx] = 1;..
문제링크 : https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; vectorv; int cal(string s1, string s2, string s3) //3개 문자열 비교 { int result = 0; for(int i=0; i32) return 0; int result = MAX; for(int i=0; i>N; v.resize(N); for(int i..