고동치는고동

문제 링크 : https://www.acmicpc.net/problem/14650 14650번: 걷다보니 신천역 삼 (Small) 욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 금강삼도 식후경, 걷다보니 신천역 삼, 그리고 특히 일�� www.acmicpc.net 먼저 특정 수에 대해 3의 배수인지 판별하는 방법을 알아보자. 각 자리수의 합이 3의 배수이면 3의 배수이다. 270, 999, 531, 8787의 경우를 보면 이 사실이 참임을 알 수 있다. 0, 1, 2를 이용해 구성하는 n자릿수의 경우의 수는 n-1자릿수의 경우에 3을 곱한 값이다. $$F_1 = 2$$ $$F_n = 3*F_{n-1}$$ ..

문제 링크 : https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 필요 알고리즘 : 유클리드 호제법 자연수 A와 B에 대해 A/B라는 분수가 있을 때 이를 기약분수로 형태로 변환하는 문제이다. 두개의 입력되는 분수에 대하여 A와 B를 구하는 방법은 쉽다. 그러나 A/B꼴의 분수를 기약분수로 변환하는 과정에서 문제가 생긴다. 기약분수로 변환하기 위해서는 먼저 A와 B의 최대공약수를 구해야된다. 기존의 방법으로 최대공약수를 구하기 위해서는 min(A, B) 횟수 만큼의 연산이 수행되어야 한다. 입력되는 ..

다익스트라와 dp를 사용한 문제 dp[x][y][k]로 dist배열을 선언한다.x,y까지 벽을 k만큼 뚫으면서 갔을 때 최단거리 기본적으로 bfs를 돌리면서 dp배열을 업데이트 시켜준다.que에는 다 넣을 필요 없이 dp배열을 업데이트 시킬 때마다 넣어준다. 출처 : http://wookje.dance/2017/02/22/boj-14442-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-2/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869..

출력범위가 int를 벗어나는 것을 주의하면 된다. 아무 노드나 루트 노드로 잡고 A노드에 있을 때, 자식 노드가 B, C, D가 있으면A노드는 자식 B, C, D가 요구하는 우물 중 가장 큰 수만큼 우물을 지으면 되고,A노드는 자신의 부모에게 자신이 필요한 우물에서 자신과 자식노드에 있는 우물의 수만큼을 뺀 값을 요구한다. 위 방식으로 dfs를 하면 최적의 값이 나온다.

쉬운 문제였지만 디스크립션을 이해하느라 오래 걸렸다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include int r, c, k;bool chk[1001][1001]; int dx[5] = { 0, -1,1,0,0 };int dy[5] = { 0,0,0,-1,1 };int gd[4];int cnt = 0; void f(int x, int y, int i) { chk[x][y] = true; int nx = x + dx[gd[i]]; int ny = y + dy[gd[i]]; if (nx == -1 || nx == r || ny == -1 || ny == c || chk[nx][ny]) { i..

12345678910111213141516#include typedef unsigned long long ull; int main(void) { int n; long long int sum = 0; scanf("%d", &n); ull prev = 0; for (int i = 1; i

곰팡이가 이동하는 것을 보면 좌푯값 i, j의 i+j가 짝수인 줄과 홀수인 줄이 독립적이라는 것을 알 수 있다.그리고 시간이 무한히 흘러간다고 가정하면 곰팡이가 한번 증식할 때마다 i의 좌표가 짝수->홀수, 홀수->짝수로 감을 알 수 있다. 따라서 초기 곰팡이의 위치가 4가지 경우가 모두 있으면 된다.i+j가 홀수고 i가 홀수i+j가 홀수고 i가 짝수i+j가 짝수고 i가 홀수i+j가 짝수고 i가 짝수 123456789101112131415161718192021222324252627#include #include using namespace std;bool chk[2][2]; int main(void) { int n, m, k; scanf("%d %d %d", &n, &m, &k); for (int i =..

간단한 매핑문제배열을 -1로 초기화 해놨지만 입력되는 증상이 배열의 크기를 초과해 고칠 수 없지만 0을 받아오는 경우가 생겼다.고쳐야하는 증상 S가 범위가 없음을 유의하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include using namespace std;int n, m;int arr[105];int brr[105]; int main(void) { int a; scanf("%d", &n); memset(arr, -1, sizeof(arr)); for (int i = 0; i

트리에서는 사이클이 존재하지 않기 때문에 단절선이 아닌 선은 없다.단절점 같은 경우 연결된 간선이 2개 이상이면 단절점이다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #define n_ 100005using namespace std; vector tree[n_]; int main(void) { int n, q, t, k; scanf("%d", &n); for (int i = 0; i

간단한 문제였지만 scanf가 아니라 cin을 써서 시간초과가 났다.검색해보니 cin이 scanf에 비해 엄청나게 느리다.앞으로는 scanf만 써야겠다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include typedef long long ull;using namespace std; ull sum = 0; int safe(int n,int m){ if (n