알고리즘
[BOJ] 15998 카카오머니
문제 링크 www.acmicpc.net/problem/15998 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제를 풀기 위해서는 각각의 출금 금액을 기록해두고, 이 금액들의 최대공약수를 구해야한다. 유클리드 호제법을 사용하면 빠른 시간안에 최대공약수를 구할 수 있다. ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } 입/출금액은 최대 10^18원 까지 가능하므로 long long형을 사용했다. 출금 금액에서 구한 최대공약수를 뺐을 때도 필요한 금액을 낼 수 있다면, 필요 이상으로 인출을 한 것이므로 이 경우 답이 존재하지 않는다. 이러한 경우가 발생하지 않는다면 구한 최대공약수가 답이 된다. 또한 출금을 아예 하지 않았다면 ..
[BOJ] 15997 승부 예측
문제 링크 www.acmicpc.net/problem/15997 모든 알고리즘 문제는 C++로 구현되어 있습니다. 오늘은 2018년 카카오 코드 페스티벌에서 출제된 문제를 풀어봤다. 문제를 처음 봤을 때는 어떻게 풀어야 할지 감이 잘 잡히지 않았지만 리그에 참여하는 국가와 경기 수가 4, 6이라는 작은 수로 정해져 있어 모든 경기 결과를 완전탐색하면 문제를 해결할 수 있을 것이라 생각했다. 문제에서 주어진 각 경기에 대한 정보는 구조체를 이용하기로 하고 아래와 같은 구조체를 생성했다. typedef struct game { int x, y; double win, draw, lose; }Game; x와 y는 참가하는 국가를 입력 순으로 번호를 매겨서 저장하기로 했으며, win, draw, lose에는 각각..
[BOJ] 1034 램프
문제 링크 www.acmicpc.net/problem/1034 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제를 풀기 위해 나는 먼저 주어진 2차원 배열의 열을 2진수로 바꿔서 생각했다. 예제로 주어진 배열에서 보면 첫 번째 열은 위에서부터 0, 1, 1이므로 011(2), 두 번째 열은 위에서부터 1, 0, 0이므로 100(2)와 같이 바꿔보면 특정 열의 스위치를 누르는 것은 그 열의 수와 bit 1이 n개인 수(2^n - 1)와 XOR 연산을 하는 것이라고 생각할 수 있다. 행과 열이 최대 50개까지 늘어날 수 있으므로 각각의 열을 나타내는 수는 long long 형으로 설정했다. 이렇게 생각을 해보면 이 문제는 임의의 열들을 골라 bit 1이 n개인 수(2^n - 1)와 K번 XOR 연산..