어쨌든 공부하는 블로그

https://www.acmicpc.net/problem/9095풀이일단 그냥 무턱대고 값을 구해보면dp[1] = 1dp[2] = 2dp[3] = 4dp[4] = 7dp[5] = 13으로, 규칙성을 발견할 수 있다dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]과 같은 점화식을 찾을 수 있다 왜 성립하는지는 모르고 일단 정답은 맞췄는데5를 만드는 경우의 수를 구할 때4를 만드는 모든 경우의 수에 +1를 해주면 5를 만들 수 있고3을 만드는 모든 경우의 수에 +2를 해주면 5를 만들 수 있고2를 만드는 모든 경우의 수에 +3을 해주면 5를 만들 수 있다(4 이상의 차이부터는 하나의 숫자만 더해서 목표 숫자에 도달할 수 없음)따라서 4, 3, 2를 만들 수 있는 모든 경우의 수를 더..

https://www.acmicpc.net/problem/2579풀이n번째 계단을 밟았을 때의 최대 점수를 구하는 방식을 반복하면 된다 dp[n]은 n번째 계단을 밟았을 때 최대 점수를 뜻하고, arr[n]은 n번째 계단의 점수라고 치자 dp[1] = arr[1]이다dp[2] = arr[2] + arr[1]이다dp[3] = arr[3] + arr[2] 또는 arr[3] + arr[1] 둘 중 큰 값이다dp[4] = arr[4] + arr[3] + arr[1] 또는 arr[4] + arr[2] + arr[1] 둘 중 큰 값이다dp[5] = arr[5] + arr[4] + arr[2] + arr[1] 또는 arr[5] + arr[3] + arr[2] 또는 arr[5] + arr[3] + arr[1] 중 큰 ..

https://www.acmicpc.net/problem/2667 제출 코드#include #include #include using namespace std;int n;string arr[26];int dx[4] = { 1, -1, 0, 0 };int dy[4] = { 0, 0, 1, -1 };int dfs(int x, int y){ // 배열 범위를 초과하거나 0일 경우 리턴값 0 if (x = n || y = n || arr[x][y] == '0') return 0; arr[x][y] = '0'; int cnt = 1; // 인자로 들어온 좌표의 상하좌우를 체크해서 cnt 세기 for (int i = 0; i > n; for (int i = 0; i..

https://www.acmicpc.net/problem/11724제출 코드(DFS)#include #include using namespace std;vector vec[1001]; // 연결된 정점들을 vector에 저장bool visit[1001]; // 방문 여부 체크용void dfs(int node){ visit[node] = true; // 연결된 노드들을 체크 for (int i = 0; i > n >> m; while(m--) { int u, v; cin >> u >> v; // 방향 없는 그래프이기 때문에 u와 v 양쪽에 push vec[u].push_back(v); vec[v].push_back(..

https://www.acmicpc.net/problem/11660 풀이1우선 누적합을 이용해 2차원 배열에 값을 채워넣는다(배열의 (i, j)에는 (0, 0)부터 (i, j)번째까지의 모든 값이 담긴다. 즉, (i + 1, 0) 위치에는 (i, n)까지의 합에 (i + 1, 0) 번째 수가 더해진 값이 들어가게 된다)답은 각 행의 x2의 누적합 - x1의 누적합을 행의 갯수만큼 반복하여 더해주면 된다위 배열이 주어졌다고 가정했을 때, 누적합을 이용해 배열을 채우면 아래와 같다제출 코드#include using namespace std;int ps[1025][1025];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ..

https://www.acmicpc.net/problem/14929 풀이출력값은 x1 * x2 + x1 * x3 + ... x1 * xn + x2 * x3 + x2 * x4 + ...x2 * xn ... x(n-1) * xn 이므로정리해서 x1(x2 + x3 + ... xn) + x2(x3 + x4 + ... xn) 와 같이 표현할 수 있다이때 xi부터 xn까지 하나하나 더하는 과정을 n번 반복하면 시간초과가 되기 때문에 누적합을 이용한다 제출 코드#include using namespace std;int arr[100001];int ps[100001];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; ..

https://www.acmicpc.net/problem/3474 풀이오른쪽 끝에 나오는 0의 개수는 10이 얼마나 곱해졌는가를 구하면 된다그렇다면 10이 얼마나 곱해졌는가는 2와 5가 몇 개 곱해졌는가를 구하면 된다이때 2가 곱해진 횟수와 5가 곱해진 횟수 중 더 작은 횟수가 10이 곱해진 횟수라고 보면 되는데, 2는 모든 짝수가 해당되므로 팩토리얼 연산에서는 무조건 5가 곱해진 횟수보다 많다 따라서 5가 곱해진 횟수를 세면 되는데, N!을 계산하기 위해 1부터 N까지 루프문을 돌며 5가 등장하는 횟수를 세면 시간초과가 된다(N의 최댓값이 10억이기 때문) N이 125라면, 1부터 125까지를 곱해주어야 한다. 1부터 125까지의 수 중에 5의 배수가 등장하는 횟수는 125를 5로 나누어 쉽게 구할 수..

우선 두 수의 최소공배수(LCM)는 두 수의 곱을 최대공약수로 나눠주면 구할 수 있다따라서 최대공약수(GCD)를 구하는 것이 중요하다 a와 b의(단, a > b)최대 공약수는 a % b(mod), 즉 나머지가 0이 될 때까지 아래와 같이 반복하여 구할 수 있다1. a % b = r, 나머지의 값을 구한다2. b를 나머지(r)로 나눈 값의 나머지(r')를 구한다3. r을 r'로 나눈 값의 나머지(r'')를 구한다... 1. 재귀함수로 구현int gcd(int a, int b){ if (a % b == 0) return b; return gcd(b, a % b);} 2. 반복문으로 구현int gcd(int a, int b){ int r = a % b; while(r) ..

https://www.acmicpc.net/problem/21920풀이1x의 소인수를 저장해두고, 입력된 수들을 x의 소인수들로 나눠서 서로소인지 여부를 확인한다 제출 코드#include #include using namespace std;int arr[500001];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, x; cin >> n; for (int i = 0; i > arr[i]; cin >> x; vector v; // x의 소인수 구하기 for (int i = 2; i  풀이2서로소라는 것은 두 수의 최대공약수가 1인 수라는 의미이다이를 그대로 해석하여 gcd ..

https://www.acmicpc.net/problem/5347풀이최소공배수(LCM)와 최대공약수(GCD)를 유클리드 호제법을 이용해 푸는 문제다 두 수의 최소 공배수는 두 수의 곱을 최대 공약수로 나누면 구할 수 있다 a와 b의(단, a > b)최대 공약수는 a % b(mod), 즉 나머지가 0이 될 때까지 아래와 같이 반복하여 구할 수 있다1. a % b = r, 나머지의 값을 구한다2. b를 나머지(r)로 나눈 값의 나머지(r')를 구한다3. r을 r'로 나눈 값의 나머지(r'')를 구한다...  제출 코드#include using namespace std;long long gcd(long long a, long long b){ if (a % b == 0) return b; ..