18 Oct 2020 |
PS
AtCoder Beginner Contest 180 B번 Various distances
문제
https://atcoder.jp/contests/abc180/tasks/abc180_b
풀이
n개의 정수 포인트가 주어졌을 때 맨하탄 거리, 유클리드 거리, 체비쇼프 거리를 각각 구하는 문제
각 거리의 공식은 문제에 적혀있으므로 그대로 구현하면 된다.
코드
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll,ll,ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc180/tasks/abc180_b
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
ll Manhattan = 0;
ld Euclidian = 0;
ll Chebyshev = 0;
rep(i,n){
ll e;
cin >> e;
e = abs(e);
Manhattan += e;
Chebyshev = max(Chebyshev, e);
Euclidian += (e*e);
}
Euclidian = sqrt(Euclidian);
cout << fixed;
cout.precision(15);
cout << Manhattan << "\n";
cout << Euclidian << "\n";
cout << Chebyshev << "\n";
}
18 Oct 2020 |
PS
AtCoder Beginner Contest 180 A번 box
문제
https://atcoder.jp/contests/abc180/tasks/abc180_a
풀이
너무 간단한 산수 문제
문제를 잘 읽으면 바로 풀 수 있는 문제.
코드
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll,ll,ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc180/tasks/abc180_a
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,a,b;
cin >> n >> a >> b;
cout << n - a + b;
}
17 Oct 2020 |
PS
백준 9661번 돌 게임 7
문제
https://www.acmicpc.net/problem/9661
풀이
상근이와 창영이가 돌을 4^x 개씩 가져갈 수 있다고 할 때 돌이 n개일 때 돌을 못가져가면 지게된다. 이때 누가 이기는지 맞추는 문제이다.
1개일땐 상근이가 남은 1개를 가져가면서 승리
2개일땐 창영이가 마지막 1개를 가져가면서 승리
3개일땐 상근이가, 4개일땐 상근이가 5개일땐 창영이가 이긴다.
이후 6개일때부터 계산해보면 규칙이 보일것이다.
코드
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll,ll,ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://www.acmicpc.net/problem/9661
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
ll ans = n%5;
if(ans == 0 || ans == 2) cout << "CY";
else cout << "SK";
return 0;
}
15 Oct 2020 |
PS
백준 2749번 피보나치 수 3
문제
https://www.acmicpc.net/problem/2749
풀이
단순히 n번째 피보나치 수를 출력하면 되는 문제인데
n의 범위가 1,000,000,000,000,000,000 까지라 dp로도 재귀로도 해결할 수 없다.
이는 피사노 주기를 이용하여 해결하여야 한다.
피사노 주기란 피보나치 수에 mod k를 한 수는 항상 일정 주기를 갖는데 그 주기를 의미한다.
이 문제의 mod 1000000에 대해서는 피사노 주기는 150만이므로 150만주기로 반복하게된다.
https://en.wikipedia.org/wiki/Pisano_period
코드
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;
// https://www.acmicpc.net/problem/2749
#define MOD 1000000
int dp[1500001] = {0,1,1,2,3,5,}; //150만 주기로 반복
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
for(int i = 5;i<=1500000;i++){
dp[i] = (dp[i-1]+dp[i-2]) % MOD;
}
cout << dp[n%1500000];
return 0;
}
13 Oct 2020 |
PS
백준 16480번 외심과 내심은 사랑입니다
문제
https://www.acmicpc.net/problem/16480
풀이
삼각형 ABC에서 외심 R과 내심 r 이 존재할 때, (외심과 내심 사이 직선거리^2)을 구하는 문제
이는 오일러 삼각형 정리 (Euler’s triangle theorem) 를 구현하는 문제이다.
https://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%EC%82%BC%EA%B0%81%ED%98%95_%EC%A0%95%EB%A6%AC
오일러 삼각형 정리에서 외심과 내심 사이의 거리의 제곱은 R(R-2r)이다.
코드
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
// https://www.acmicpc.net/problem/16480
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll R,r;
cin >> R >> r;
// https://en.wikipedia.org/wiki/Euler%27s_theorem_in_geometry
cout << (R*R) - (2*R*r);
return 0;
}