-
[BOJ] 2492: 보석
2492: 보석 풀이 이 풀이를 참고하자. 복붙 날먹 꺼-억 아 이 문제는 사각형이 격자를 벗어나면 안 되니까 주의하자. 코드 #include <bits/stdc++.h> using namespace std; int n, m, t, k; int dap, dap_x, dap_y; struct abc { int x, y; } a[111]; void go(int x, int y) { int cnt = 0; for (int i = 1; i <= t; i++) { if (x <= a[i].x && a[i].x <= x+k && y <= a[i].y && a[i].y...
-
[BOJ] 2496: 금강석
2496: 금강석 풀이 (x, y)의 좌표계를 변환하자. (x, y) => (x+y, x-y)로 좌표를 변환시키면 좌표계가 45도 기울어지고, 점 사이의 간격이 root(2)배만큼 늘어난다. 좌표계를 돌리고 나면 마름모가 정사각형이 되므로, 문제를 풀기 한결 수월해진다. T가 100밖에 안 된다는 점을 주목하자. 정답에 포함되는 어떤 금강석들의 집합이 있다고 하자. 이 금강석들을 포함하는 사각형은, 얘네들을 모두 포함하는 선에서 이리저리 잘 옮길 수 있을 것이다. 정답을 벗어나지 않는 선에서, 사각형을 최대한 오른쪽 아래로 땡겨보자. 항상 두 개의 금강석이 왼쪽과 위쪽 변에...
-
[BOJ] 14736 : Coke Challenge
14736 : Coke Challenge 풀이 뭐 어떻게 식을 잘 세워주면 되는데 어… 코드를 보는 게 더 빠를 것 같다. 코드 #include <cstdio> #include <algorithm> int n, k, a, ans = 1e9; int main() { scanf("%d %d %d", &n, &k, &a); for (int i = 0; i < n; i++) { int t, s; scanf("%d %d", &t, &s); ans = std::min(ans, k/a+(k/(a*t)+(k%(a*t)?0:-1))*s); } printf("%d", ans); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online...
-
[BOJ] 15997 : 승부 예측
15997 : 승부 예측 풀이 6개 각각의 경기마다 W, D, L 3개의 상태가 있으므로 최종 스코어는 총 3^6개의 경우가 나올 수 있다. 개수가 많지 않으니 완전탐색을 해주자. 마지막에 동률인 경우를 예외처리 하는 게 몹시 화가 나지만 인내심을 가지고 풀어보자. 코드 #include <bits/stdc++.h> #define fst first #define snd second using namespace std; map<string, int> m; struct abc { int x, y; double w, d, l; } a[6]; int s[4]; double r[4]; pair<int, int> t[4]; void go(int...
-
[BOJ] 8101 : Rods
8101 : Rods 풀이 요약: 양 끝점이 고정된 길이 L의 선분이 있다. 이 선분의 가운데를 이쁘게 늘려서 길이 L+d의 곡선을 만든다. 그럼 길이 L의 현과 길이 L+d의 호가 만들어진다. 이 때, 현의 중심과 호의 중심까지의 거리 x는 얼마일까? 알고리즘에 수학을 싸서 드셔보세요!! 주어진 호를 예쁘게 연장해서 예쁜 원을 만들어주자. 원의 중심에서 현의 끝점까지 예쁜 반지름 r1, r2도 그어주자. 현을 이등분하는 예쁜 반지름 r3도 그어주자. r3와 r2, r3와 r1 사이의 각을 세타라고 하자. 삼각함수를 이용해서 식을...
-
[BOJ] 15998 : 카카오머니
15998 : 카카오머니 풀이 주어지는 입력을 a[i], b[i]라고 하자. b[i]-b[i-1] == a[i]인 경우는 돈을 뽑아서 쓰지 않는 정상적인(?) 경우이다. b[i]-b[i-1] != a[i]인 경우는 비정상적인(?) 경우이다. 여기서 비정상적인(?) 경우도 두 경우로 나뉜다. 하나는 인출하지 않는 상황에서 남은 금액이 맞지 않는 경우, 이건 그냥 짜주자. 인출하는 경우에, 은행에서 인출하는 금액 k는 b[i]-b[i-1]-a[i]이다. 오 그렇다면 이러한 k가 여러개 있을 수 있는데, 우리가 구하는 건 공통된 k이므로 이러한 k들의 gcd를 구해주자. 그러한 gcd 값을 gcd_k라고 하자. 그럼 답이 모순되는...
-
[BOJ] 15267 : Justified Jungle
15267 : Justified Jungle 풀이 트리를 일단 나눴다면, 나눠진 후의 모든 컴포넌트에 속한 노드 수는 같아야 한다. 즉, 노드는 n의 약수로만 나눠질 수 있다. 100만 이하 자연수의 약수 개수가 최대 240개니까 O(240*n) 잘 커팅하면 6초 안에 될 거 같은데 안 됨 흠… 아무튼 나이브하게는 안 돌아가므로 조금 더 생각을 해야한다. 트리를 돌며 gcd(서브트리의 노드 개수, n)의 개수를 세어주자. 음… 그냥 코드를 보는 게 더 빠르겠다. 코드 #include <cstdio> #include <vector> using namespace std; int n,...
-
[BOJ] 15264 : Gambling Guide
15264 : Gambling Guide 풀이 1에서 N으로 가는 기댓값을 구해야 하는데 기댓값을 구할 수가 없다! 그러니까 N에서부터 1로, 거꾸로 가면서 구해주자. 코드 #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; const int n_ = 3e5+3; int n, m, sdeg[n_]; double dp[n_], sdp[n_]; struct abc { int idx; double val; bool operator <(abc a)const { return val > a.val; } }; priority_queue<abc> pq; vector<int> gph[n_]; int main() { scanf("%d %d", &n, &m); for...
-
[BOJ] 10986 : 나머지 합
10986 : 나머지 합 풀이 (a[i] + ... + a[j]) % m = 0의 필요충분조건은 (a[1]+...+a[j]) % m = (a[1]+...+a[i-1]) % m이다. 오잉? 주어진 문제가 나머지가 x인 prefix sum의 개수를 k라고 할 때, k에서 2개를 고르는 경우의 수들의 합을 구하는 문제로 바뀌었다. 코드 #include <cstdio> typedef long long ll; int n, m, x; ll r, s, a[1002]={1}; int main() { scanf("%d %d", &n, &m); while (n--) scanf("%d", &x), a[s=(s+x)%m]++; while (m--) r+=(a[m]*(a[m]-1))/2; printf("%lld", r); return...
-
[BOJ] 2960 : 에라토스테네스의 체
2960 : 에라토스테네스의 체 풀이 하앙 나도 에라토스테네스처럼 고수이고 싶다 코드 #include <cstdio> int n, k, c, v[1001]; int main() { scanf("%d %d", &n, &k); for (int i = 2; i <= n; i++) { for (int j = 1; i*j <= n; j++) { if (!v[i*j]) c++; v[i*j] = 1; if (c == k) return !printf("%d\n", i*j); } } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨,...
-
[BOJ] 10531 : Golf Bot
10531 : Golf Bot 풀이 골프 봇이 칠 수 있는 거리를 체킹 배열 a와 b에 체크했다고 생각하자. 두 배열을 bool 곱셈한 배열을 c배열이라고 하자. 만약 a[i] != 0 && b[j] != 0라면 c[i+j] != 0도 성립한다. 코드 #define _USE_MATH_DEFINES #include <cstdio> #include <cmath> #include <complex> #include <vector> #include <algorithm> using namespace std; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef complex<double> base; void fft(vector<base> &a, bool invert) { int n = sz(a); for (int i=1,j=0;i<n;i++){ int...
-
[BOJ] 15668 : 방 번호
15668 : 방 번호 풀이 적당히 큰 수까지 어떻게 잘 돌려주면 된다. 코드 #include <cstdio> #include <cstring> #include <algorithm> int n, ans, cnt[10]; int main() { scanf("%d", &n); for (int i = 1; i < std::min(n, 98765); i++) { memset(cnt, 0, sizeof(cnt)); int a = i, b = n - i, flag = 1; while (a) cnt[a % 10]++, a /= 10; while (b) cnt[b % 10]++, b /= 10; for (int j = 0;...
-
[BOJ] 15667 : 2018 연세대학교 프로그래밍 경진대회
15667 : 2018 연세대학교 프로그래밍 경진대회 풀이 폭죽이 폭발하는 경우를 수식으로 잘 나타내서 정리해보자. n = x^2 + x + 1 = x(x+1) + 1 n - 1 = x * (x + 1) 이제 리니어하게 탐색해주자. 코드 #include <cstdio> int main() { int n; scanf("%d", &n); n--; for (int i = 1; i <= n; i++) { if (i * (i + 1) == n) { printf("%d", i); return 0; } } return 0;...
-
[BOJ] 14557 : Memory
14557 : Memory 풀이 봄이 그렇게도 좋냐 멍청이들아 코드 main(a,b){scanf("%d%d",&a,&b);printf("%d %d",a*b/2,a*b-1);} 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1850 : 최대공약수
1850 : 최대공약수 풀이 뚜룹뚜빠라빠라 코드 #include <cstdio> typedef long long ll; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } ll a, b; int main() { scanf("%lld %lld", &a, &b); int r = gcd(a, b); while (r--) printf("1"); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 9047 : 6174
9047 : 6174 풀이 오후수업개꿀 코드 #include <cstdio> #include <functional> #include <algorithm> using namespace std; int main() { int tc; for (scanf("%d", &tc); tc--;) { int i, c = 0, a[5], b[5]; for (i = 0; i < 4; i++) scanf(" %1d", &a[i]); while (a[0] != 6 || a[1] != 1 || a[2] != 7 || a[3] != 4) { b[0] = a[0], b[1] = a[1], b[2] = a[2], b[3] = a[3]; sort(a, a +...
-
[BOJ] 1377 : 버블 소트
1377 : 버블 소트 풀이 몇 번 움직였는지 세어보자 코드 #include <cstdio> #include <algorithm> using namespace std; int n, i, r; pair<int, int> p[500005]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &p[i].first), p[i].second = i; sort(p, p + n); for (i = 0; i < n; i++) r = max(r, p[i].second - i); printf("%d", r + 1); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online...
-
[BOJ] 3047 : ABC
3047 : ABC 풀이 꺄르르르르르르륵 코드 #include <cstdio> #include <algorithm> int a[5]; char b[5]; int main() { scanf("%d %d %d %s", &a[0], &a[1], &a[2], b); std::sort(a, a + 3); printf("%d %d %d", a[b[0] - 'A'], a[b[1] - 'A'], a[b[2] - 'A']); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1964 : 5각형, 5각형, 5각형...
1964 : 5각형, 5각형, 5각형… 풀이 알잖아 너를 이토록 사랑하며 기다린 나를~ 코드 main(n){printf("%d",scanf("%d",&n)+n*(3ll*n+5)/2%45678);} 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1373 : 2진수 8진수
1373 : 2진수 8진수 풀이 가나다라마바사 코드 #include <cstdio> int i, j; char c[1000005] = { '0','0' }; int main() { scanf("%s", c + 2); while (c[i]) c[i++] -= '0'; for (j = i % 3; j < i; j += 3) printf("%d", c[j]*4 + c[j+1]*2 + c[j+2]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1357 : 뒤집힌 덧셈
1357 : 뒤집힌 덧셈 풀이 돌리고 돌리고 돌리고~ 코드 #include <cstdio> int f(int n) { int r = 0; while (n) r *= 10, r += n % 10, n /= 10; return r; } int main() { int a, b; scanf("%d %d", &a, &b); printf("%d", f(f(a) + f(b))); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1312 : 소수
1312 : 소수 풀이 언젠가는 돌아갈게 사랑할 자격 갖춘 나 되어 코드 #include <cstdio> int a, b, c, n; int main() { scanf("%d %d %d", &a, &b, &n); while (n--) a %= b, a *= 10, c = a / b; printf("%d", c); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 13324 : boj 수열 2
13324 : boj 수열 2 풀이 끙 풀이를 뭐라고 적지 코드 #include <cstdio> #include <queue> using namespace std; int n, i, a, ans[1000001]; priority_queue<int> pq; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) { scanf("%d", &a); a -= i; pq.push(a); pq.push(a); pq.pop(); ans[i] = pq.top(); } --i; while (--i) if (ans[i] > ans[i + 1]) ans[i] = ans[i + 1]; for (i = 1; i <= n; i++) printf("%d\n", ans[i]...
-
[BOJ] 13323 : boj 수열 1
13323 : boj 수열 1 풀이 13324번 풀이를 참고하자 코드 #include <cstdio> #include <queue> using namespace std; int n; long long sum; priority_queue<int> pq; int main() { scanf("%d", &n); for (int i = 0, a; i < n; i++) { scanf("%d", &a); a -= i; pq.push(a); if (!pq.empty() && pq.top() > a) { sum += pq.top() - a; pq.pop(); pq.push(a); } } printf("%lld", sum); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online...
-
[BOJ] 14815 : Fresh Chocolate (Small)
14815 : Fresh Chocolate (Small) 풀이 룰루랄라 코드 #include <cstdio> #include <algorithm> using namespace std; int main() { int tc, t, n, p, c[5]; scanf("%d", &tc); for (t = 1; t <= tc; t++) { c[0] = c[1] = c[2] = c[3] = 0; scanf("%d %d", &n, &p); for (int i = 0, a; i < n; i++) scanf("%d", &a), c[a % p]++; int r = c[0]; if (p == 2) { r += (c[1]...
-
[BOJ] 14816 : Fresh Chocolate (Large)
14816 : Fresh Chocolate (Large) 풀이 뭔가 제너럴한 규칙을 찾으려고 했는데 잘 모르겠당 p가 2~4밖에 안 되므로 그냥 경우를 나눠서 잘 따져주자. 코드 #include <cstdio> #include <algorithm> using namespace std; int main() { int tc, t, n, p, c[5]; scanf("%d", &tc); for (t = 1; t <= tc; t++) { c[0] = c[1] = c[2] = c[3] = 0; scanf("%d %d", &n, &p); for (int i = 0, a; i < n; i++) scanf("%d", &a),...
-
[BOJ] 11585 : 속타는 저녁 메뉴
11585 : 속타는 저녁 메뉴 풀이 원순열을 구현하려면 귀찮으니까 똑같은 문자열을 두 번 이어붙여주자 그리고 kmp를 돌려서 substring으로 등장하는 횟수를 구해주자 코드 #include <cstdio> const int n_ = 1e6 + 5; int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } int n, i, j, cnt, fail[n_]; char a[n_], b[n_ * 2]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) scanf(" %c", &a[i]); for (i =...
-
[BOJ] 1402 : 아무래도이문제는A번난이도인것같다
1402 : 아무래도이문제는A번난이도인것같다 풀이 a * 1 * 1 * 1 ... 이런 식으로 모든 수를 만들 수 있다. 코드 main(t){for(scanf("%d",&t);t--;)puts("yes");} 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 7572 : 간지
7572 : 간지 풀이 나는 몰랐네 그대 마음 변할 줄은 난 정말 몰랐었네 코드 main(n) { scanf("%d",&n); printf("%c%d",(n+8)%12+'A',(n+6)%10); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1297 : TV 크기
1297 : TV 크기 풀이 수학 조아!!! 가로 세로 n:m의 비율이 주어지면 이 때의 대각선 비율을 d라고 하자. 이제 이걸 주어진 대각선 길이에 맞춰 나누고 곱하고 으쌰으쌰 해보자. 코드 #include <cstdio> #include <cmath> int main() { int k, a, b; scanf("%d %d %d", &k, &a, &b); double d = k/sqrt(a*a+b*b); printf("%d %d", (int)(a*d), (int)(b*d)); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조,...
-
[BOJ] 1225 : 이상한 곱셈
1225 : 이상한 곱셈 풀이 눈누난 코드 #include <cstdio> long long i, s, r; char a[10001], b[10001]; int main() { scanf("%s %s", a, b); for (i = 0; a[i]; i++) s += a[i] - '0'; for (i = 0; b[i]; i++) r += s * (b[i] - '0'); printf("%lld", r); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이...
-
[BOJ] 1011 : Fly me to the Alpha Centauri
1011 : Fly me to the Alpha Centauri 풀이 1 2 3 ... i-1 i i-1 ... 3 2 1 이렇게 삼각형으로 증가/감소하는 수열 s를 생각해보자. s의 원소들의 합은 i^2이다. dist = end - start일 때, dist가 음수가 되지 않는 가장 큰 i를 골라서 dist - i^2를 해주자. 남은 거리는 1와 i 사이에 숫자를 잘 골라서 채워넣을 수 있다. 코드 #include <stdio.h> #include <math.h> int main() { int tc; for (scanf("%d", &tc); tc; tc--) {...
-
[BOJ] 1188 : 음식 평론가
1188 : 음식 평론가 풀이 n과 m의 최대공약수를 이용해 문제에 접근해보자. n과 m이 서로소인 경우, 서로소가 아닌 경우로 나눌 수 있다. g = gcd(n, m)이라고 하자. f(n, m)을 n과 m에 대한 답을 구하는 함수라고 하자. f(n, m) = f(n/g, m/g) * g임은 자명하게 알 수 있다. 그러므로 g != 1인 경우의 답은 g = 1인 경우의 답을 알면 구할 수 있고 우린 모든 경우에 대해 답을 구할 수 있게 된다. 어떤 a, b에 대해서 gcd(a,...
-
[BOJ] 1145 : 적어도 대부분의 배수
1145 : 적어도 대부분의 배수 풀이 조아~ 코드 #include <stdio.h> int i,j,c,a[5]; int main() { for (i=0;i<5;i++)scanf("%d",&a[i]); for (i=1;;i++){ for(j=0,c=0;j<5;j++)if(i%a[j]==0)c++; if(c>=3)return ~printf("%d",i); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1075 : 나누기
1075 : 나누기 풀이 저 푸른 초원 위에 그림 같은 집을 짓고 코드 #include <stdio.h> int a, b, i; int main() { scanf("%d %d", &a, &b); a /= 100; a *= 100; for (; i <= 100; i++) if ((a + i) % b == 0) return ~printf("%02d", (a + i) % 100); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제,...
-
[BOJ] 1476 : 날짜 계산
1476 : 날짜 계산 풀이 역시 중국인은 똑똑해!!! 코드 #include <stdio.h> int m, s, e, x; int main() { scanf("%d %d %d", &e, &s, &m); x = (e*6916+s*4845+m*4200)%7980; return ~printf("%d", x ? x : 7980); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1676 : 팩토리얼 0의 개수
1676 : 팩토리얼 0의 개수 풀이 2랑 5의 개수를 세어주면 되는데 어차피 5의 개수가 2의 개수보다 항상 적기 때문에 5의 개수만 세어주어도 된다. 코드 #include <stdio.h> int n, c; int main() { scanf("%d", &n); while (n) n /= 5, c += n; printf("%d", c); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1947 : 선물 전달
1947 : 선물 전달 풀이 오랜만에 정상적인 풀이!! 더 자세히 알고 싶다면 구글에 완전순열 또는 교란을 검색해 보자! 증명 D[n] = (n-1) * (D[n-1] + D[n-2]) 자연수 1~n에 n+1을 더해서 완전순열을 만들어 보자. n+1은 1~n 중의 어떤 수 k의 자리에 놓인다. 이러한 k는 1부터 n까지 총 n개가 있을 수 있다. 그리고 우리는 이후의 상황을 다음의 두 경우로 나눌 수 있다. 1. n+1이 k의 자리에, k가 n+1의 자리에 놓이는 경우: k와 n+1을 제외한 나머지 n-1개의 수로...
-
[BOJ] 1057 : 토너먼트
1057 : 토너먼트 풀이 My life for Aiur! 코드 #include <stdio.h> int n, a, b, c; int main() { scanf("%d %d %d", &n, &a, &b); while (a != b) a = a/2+a%2, b = b/2+b%2, c++; printf("%d", c); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 10610 : 30
10610 : 30 풀이 어떤 숫자 N이 3의 배수인 조건 : 모든 자리에 있는 숫자들의 합이 3의 배수 10의 배수인 조건 : 첫째 자리의 숫자가 0 이 둘을 합쳐주면 30인 조건이 된다 (!!!) 코드 #include <stdio.h> int i, sum, cnt[10]; char str[100002]; int main() { scanf("%s", str); for (i = 0; str[i]; i++) cnt[str[i] - '0']++, sum += str[i] - '0'; if (!cnt[0] || sum % 3) return ~printf("-1"); for (i = 9; i >=...
-
[BOJ] 2525 : 오븐 시계
2525 : 오븐 시계 풀이 나눗셈을 오지고 지리게 해보자. 코드 #include <stdio.h> int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); b += c, a += b / 60; b %= 60, a %= 24; printf("%d %d", a, b); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2522 : 별찍기 - 12
2522 : 별찍기 - 12 풀이 오늘도 별이 바람에 스치운다 코드 #include <cstdio> int abs(int a) { return a < 0 ? -a : a; } int main() { int n, i, j, k; scanf("%d", &n); for (i = 1; i < n * 2; i++) { for (j = 0; j < abs(n - i); j++) printf(" "); for (k = 0; k < n - j; k++) printf("*"); puts(""); } return 0; }...
-
[BOJ] 2581 : 소수
2581 : 소수 풀이 소수를 멋지게 구해보자. 코드 #include <stdio.h> int n, m, sum, min; void f(int k) { if (k == 1) return; for (int i = 2; i <= k / 2; i++) if (k % i == 0) return; if (!min) min = k; sum += k; } int main() { scanf("%d %d", &n, &m); for (int i = n; i <= m; i++) f(i); if (!sum) printf("-1"); else printf("%d\n%d", sum, min);...
-
[BOJ] 13458 : 시험 감독
13458 : 시험 감독 풀이 행복을 줄 수 없었어 그런데 사랑을 했어 네 곁에 감히 머무른 내 욕심을 용서치마 코드 #include <stdio.h> int n, i, a[1000001], b, c; long long ans; int main() { scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", a + i); scanf("%d %d", &b, &c); for (i = 0; i < n; i++) { ans++, a[i] -= b; if (a[i] > 0) ans += a[i] / c +...
-
[BOJ] 1064 : 평행사변형
1064 : 평행사변형 풀이 hypot(a, b)는 a와 b를 높이, 너비로 하는 빗변의 길이를 구해주는 함수이다. 평행사변형이 만들어질 수 없는 경우를 찾아보자. 둘 이상의 점이 겹치거나, 세 점이 한 직선 위에 있으면 (= 기울기가 같으면) 사각형이 될 수 없다. ccw에서 기울기를 구하는 식을 가져다 쓰자! 여기에 개꿀개꿀 공식이 써있으니 참고하자! 둘 이상의 점이 겹치는 경우도 한 직선 위에 있는 경우이므로 별개로 처리해줄 필요는 없다. (개꿀!) 이제 평행사변형의 둘레의 길이를 찾아보자. 먼저, 남아있는 하나의 점을 찾을 필요가...
-
[BOJ] 13269 : 쌓기나무
13269 : 쌓기나무 풀이 앞에서 보이는 최대 값들로 채워준 다음 옆에서 보이는 최대 값들을 만족하게 바꿔준다 그리고 조건을 만족하는지 체크해보자! 코드 #include <stdio.h> #define REP(k,n) for(k=0;k<n;k++) #define RRP(k,n) for(k=n-1;k>=0;k--) int main() { int n, m, i, j, a[500][500], b[500], c[500]; scanf("%d %d", &n, &m); REP(i,n) REP(j,m) scanf("%d", &a[i][j]); REP(j,m) { scanf("%d", &b[j]); REP(i,n) if (a[i][j] == 1) a[i][j] = b[j]; } RRP(i,n) { scanf("%d", &c[i]); REP(j,m) if (a[i][j] > c[i]) a[i][j] = c[i]; } REP(j,m)...
-
[BOJ] 13268 : 셔틀런
13268 : 셔틀런 풀이 달빛이 흡사 비오듯 쏟아지는 밤에도 우리는 헐어진 성(城)터를 헤매이면서 언제 참으로 그 언제 우리 하늘에 오롯한 태양을 모시겠느냐고 가슴을 쥐어뜯으며 이야기하며 이야기하며 가슴을 쥐어뜯지 않았느냐? 코드 #include <stdio.h> #include <stdlib.h> #define a(e) for(int i=1;i<=e;i++)n-=5,f(i) #define b(e) for(int i=e;i>=1;i--)n-=5,f(i) int n, k; void f(int a) { if (n <= 0) { printf("%d", a); exit(0); } } int main() { scanf("%d", &n); n %= 100; for (int j = 0; j <= 4;...
-
[BOJ] 13560 : 축구게임
13560 : 축구게임 풀이 랑주의 정리! S[i] = a[1~i]의 합, S[1~k] >= kC2 S[n] = nC2 증명 코드 #include <stdio.h> #include <algorithm> int main() { int n, i, s = 0, a[10000]; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); std::sort(a, a + n); for (i = 0; i < n; i++) { s += a[i]; if (s < (i+1)*i/2) return ~printf("-1"); } printf("%d", s == n*(n-1)/2 ? 1 : -1);...
-
[BOJ] 14731 : 謎紛芥索紀 (Large)
14731 : 謎紛芥索紀 (Large) 풀이 지수가 몹시 크다! 하지만 f`(2)라고 하지 않았던가! 2의 제곱꼴이란 뜻이다! 숫자를 제곱제곱제곱제곱 하면서 1000000000를 log로 줄이자! 나머지 연산에 주의하자! 코드 #include <stdio.h> const int mod = 1e9 + 7; int n; long long s, e, x; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d", &e, &x); long long t = 1, p = 2, q = x - 1; while (q)...
-
[BOJ] 14730 : 謎紛芥索紀 (Small)
14730 : 謎紛芥索紀 (Small) 풀이 잎새에 이는 바람에도 난 괴로워했다. 코드 n, s, e, x; main() { scanf("%d", &n); while (n--) scanf("%d %d", &e, &x), s+=e*x; printf("%d", s); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 14729 : 칠무해
14729 : 칠무해 풀이 제한이 몹시 크다! 정렬하면 큰일난다! 대신, 소수점에 1000을 곱해서 정수 a로 만들어 준 다음에 카운팅 배열 cnt[a]에 체크해주자. 그래봤자 10만개이므로 cnt[0]부터 cnt[100000]까지 돌면 깔끔하게 풀 수 있다. 코드 #include <stdio.h> int n, a[100001], x, y; int main() { scanf("%d", &n); while (n--) { scanf("%d.%d", &x, &y); a[x*1000+y]++; } for (int i = 0, c = 0; i <= 100000; i++) { while (a[i]) { --a[i], ++c; printf("%d.%03d\n", i / 1000, i...
-
[BOJ] 10250 : ACM 호텔
10250 : ACM 호텔 풀이 규칙을 잘 찾아보자! 코드 #include <stdio.h> int main() { int t, h, w, n; scanf("%d", &t); while(t--) { scanf("%d %d %d", &h, &w, &n); n--; printf("%d%02d\n", n%h+1, n/h+1); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2292 : 벌집
2292 : 벌집 풀이 a[i]를 중앙에서 i번째로 떨어진 껍데기를 이루는 육각형의 수라고 두면 a[i] = a[i-1] + 6 (a[0] = 1, a[1] = 6)이라는 식이 나온다. 이제 구현해보자! 룰루랄라 코드 #include <stdio.h> int main() { int n, i; scanf("%d", &n); n--; while (1) { n -= i*6, i++; if (n <= 0) break; } printf("%d", i); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바,...
-
[BOJ] 1016 : 제곱 ㄴㄴ 수
1016 : 제곱 ㄴㄴ 수 풀이 제곱 ㄴㄴ 수를 직접 세어주려면 시간이 너무 오래 걸린다. 제곱 ㄴㄴ 수를 제외한 나머지는 모두 제곱 ㅇㅇ 수(?)이므로 제곱 ㅇㅇ 수(?)를 카운팅해서 전체 개수에서 빼주자! 룰루랄라 코드 #include <stdio.h> typedef long long ll; bool chk[1000001], aux[1000001]; int main() { ll a, b; scanf("%lld %lld", &a, &b); int ans = b - a + 1; for (ll i = 2; i*i <= b; i++) { if (aux[i]) continue; for (ll...
-
[BOJ] 1977 : 완전제곱수
1977 : 완전제곱수 풀이 음 잘 세어주면 된다 코드 #include <stdio.h> int min(int a, int b) { return a < b ? a : b; } int a, b, sm, mn = (int)1e9; int main() { scanf("%d %d", &a, &b); for (int i = 1; i*i <= b; i++) { if (i*i >= a && i*i <= b) { mn = min(mn, i*i); sm += i*i; } } if (!sm) printf("-1"); else printf("%d\n%d", sm, mn);...
-
[BOJ] 1076 : 저항
1076 : 저항 풀이 잘 계산해주자 꺄르륵 코드 #include <iostream> #include <string> using namespace std; int i, j; long long sum; string a, b, c, s[] = {"black","brown","red","orange","yellow","green","blue","violet","grey","white" }; int main() { cin >> a >> b >> c; for (i = 0; i < 10; i++) { if (a == s[i]) sum += i * 10; if (b == s[i]) sum += i; } for (i = 0; i < 10; i++) if (c...
-
[BOJ] 1475 : 방 번호
1475 : 방 번호 풀이 6과 9는 구분없이 사용 가능하므로 그것만 신경써서 카운팅 해주면 된다 코드 #include <stdio.h> #include <string.h> #define max(a,b) (a)>(b)?(a):(b) int ans, tmp, cnt[10]; char str[10]; int main() { scanf("%s", str); for (int i = 0; i < strlen(str); i++) cnt[str[i] - '0']++; for (int i = 0; i <= 9; i++) if (i != 6 && i != 9) ans = max(ans, cnt[i]); ans = max(ans, (cnt[6] + cnt[9] + 1)...
-
[BOJ] 10158 : 개미
10158 : 개미 풀이 개미가 움직이는 w*h 크기의 격자가 사방에 이어붙여져 있다고 생각해보자. w - abs(w - (x + t) % (2 * w)), h - abs(h - (y + t) % (2 * h)) 나머지 연산을 이용하면 간단하게 풀 수 있다. 코드 #include <bits/stdc++.h> int w, h, x, y, t; int main() { scanf("%d %d %d %d %d", &w, &h, &x, &y, &t); printf("%d %d", w - abs(w - (x + t) % (2...
-
[BOJ] 2786 : 상근이의 레스토랑
2786 : 상근이의 레스토랑 풀이 (첫 주문) 가격과 (일반 주문) 가격이 나누어져있다. 일반 가격으로 정렬한 뒤 1~i번째 가격의 합을 구해놓고 생각하자. 그럼 두 가지의 케이스로 나눌 수 있다. 1~i번째 메뉴들 중 (첫 주문)과 (일반 주문) 가격의 차이가 가장 큰 것을 고르는 경우 i~n번째 메뉴들 중 (첫 주문)의 가격이 가장 작은 것을 고르는 경우 이제 어찌저찌여차저차 잘 짜면 된다. 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; typedef pair<int, int>...
-
[BOJ] 2785 : 체인
2785 : 체인 풀이 데스크립션이 이상해서 한참 고민했다 (…) 고리로 이루어진 체인들이 여럿 주어진다. 고리를 최소한으로 사용해서 모든 체인들을 일렬로 연결하고 싶다. 한 고리에는 최대 두 개의 다른 고리(체인)만 연결할 수 있다. 그리디하게 생각해보자! 체인의 수가 작아지면 필요한 고리의 수도 작아진다. 그리고 체인을 모두 고리로 분해하면 체인의 개수가 하나 줄어든다.! 길이가 가장 짧은 체인의 고리부터 사용하면 된다! 같은 양의 고리를 사용하더라도 길이가 짧은 것부터 사용해야 체인의 수를 조금이나마 더 줄일 수 있다. 코드 #include <stdio.h>...
-
[BOJ] 1735 : 분수 합
1735 : 분수 합 풀이 중학교의 추억을 되새겨보자! 룰루랄라~ 코드 #include <stdio.h> int a, b, c, d; int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } int main() { scanf("%d %d %d %d", &a, &b, &c, &d); a = a*d + b*c, c = b*d, b = gcd(a, c); printf("%d %d", a/b, c/b); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA,...
-
[BOJ] 14571 : 모래시계
14571 : 모래시계 풀이 임의의 두 인접한 사이클은 하나 또는 두개의 노드를 공유할 수 있으므로 두 경우의 수를 모두 구해서 겹치는 경우를 제거하자 컴비네이션으로 구하면 쉽게 구할 수 있다. 코드 #include <stdio.h> #include <vector> using namespace std; typedef long long ll; const int n_ = 200; int n, m, one[n_], two[n_][n_]; bool gph[n_][n_]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int u, v; scanf("%d %d",...
-
[BOJ] 14570 : 나무 위의 구슬
14570 : 나무 위의 구슬 풀이 문제의 조건을 그대로 가져다 써보자. 모든 노드에 대해, 왼쪽 구슬의 수가 오른쪽 구슬의 수보다 크거나 같다. n개의 구슬 중 n/2+n%2개는 왼쪽, n/2개는 오른쪽으로 떨어지게 된다. 종단 노드를 만날 때 까지 돌려보자~~ 코드 #include <stdio.h> struct hello { int l, r; } t[200001]; int main() { int n; long long k; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d %d", &t[i].l, &t[i].r); scanf("%lld", &k); int cur...
-
[BOJ] 14568 : 2017 연세대학교 프로그래밍 경시대회
14568 : 2017 연세대학교 프로그래밍 경시대회 풀이 택희가 받는 사탕의 개수를 i로 두고 구하면 된다. n개 사탕 중에서 택희 사탕 i개와 영훈이랑 남규의 사탕 차이 2개를 뺀 사탕 갯수 n-i-2에서 (영훈 <= 남규)를 만족하는 조합의 수는 (n-i-2)/2와 같다. ex1) 5를 나누는 경우: (1,4), (2,3) ex2) 6를 나누는 경우: (1,5), (2,4), (3,3) 코드 #include <stdio.h> int n, sum; int main() { scanf("%d", &n); for (int i = 2; i <= n - 2; i += 2)...
-
[BOJ] 1019 : 책 페이지
1019 : 책 페이지 풀이 나중에 써야지~ 코드 #include <stdio.h> int N, prev; int cnt[10]; int main() { scanf("%d", &N); for (int i = 1; N; i *= 10) { int now = N % 10; N /= 10; for (int j = 0; j < now; ++j) cnt[j] += (N + 1) * i; cnt[now] += N * i + prev + 1; for (int j = now + 1; j < 10; ++j)...
-
SIGPL Winter School 2017 3일차 정리
SIGPL Winter School 2017 3일차 정리 마지막 날 Type Check Val/Computation.Inductive/Fuction 4가지 룰이랑 Eval만 사용해서 체크함 logical한 step 4개의 룰만 있으면 거의 모든 증명을 할 수 있음 나머지 불가능한 것도 axiom? 추가하면 가능 프로그램 식을 그대로 읽으면 증명하는 거랑 똑같음 ->은 non dependent function forall은 dependent function ==forall, ->, =, P -> false, True, False, /|, |/, exists== 이것만 가지고 모든 set을 만들 수 있음 set이 바로 proposition (coq에서, m zigler set은 set prop는 prop)...
-
SIGPL Winter School 2017 2일차 정리
SIGPL Winter School 2017 2일차 정리 Martin Ziegler Logic 강의 tautology - always true satisfiability - true but not always inconsistency - false emptyset : false -> true 추후에 추가 예정 다시 Coq 강의 istrue = predicate type check 동시에 evaluate P -> Q P ------------ Q 증명 불가능한 함수는 짤 수 없다 1+(n:nat)를 짤 수는 없지만 1+(n:nat)->false 는 가능 evaluation은 증명을 단순화 시키는 것, simplify type checking 할 때 evaluation 해도 안전함 eval termination...
-
SIGPL Winter School 2017 1일차 정리
SIGPL Winter School 2017 1일차 정리 주어가 명시되지 않은 문장은 대부분 Coq가 그렇다는 의미로 받아들이면 대부분 알아들을 수 있을 것이다. Coq는 실제 계산할 때 퍼포먼스 때문에 nat에서 다른 타입으로 계산을 허용한다고 한다. Coq로 짠 코드를 실행하다가 오버플로우 등의 현실적인 에러가 발생할 수 있지만, 애초에 Coq는 Theorem을 증명하는 데에 목적을 두기 때문에 Coq에 대해 문제를 제기할 필요는 없다. 문제 없이 Type Check를 통과하면 안전하다고 보장된다. 이의를 제기할 필요는 없다. Type Check를 통과하면 안전하다는 사실이 이미 다...
-
SIGPL Winter School 2017
SIGPL Winter School 2017 SIGPL Winter School 2017에 참여하여 보고, 듣고, 배우고, 느낀점을 정리한 글입니다. 관련 자료가 여기(슬라이드)와 여기(책) 있으니 필요하신 분은 참고하시기 바랍니다!