귀찮았던 문제. https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 그냥 너무나도 귀찮았던 나머지 입력이 홀수로 들어오면 2를 잘 빼줘서 5의 배수 꼴로 만들어준 다음 잘 계산했고 입력이 짝수로 들어오면 10의자리와 1의자리를 분리해서 계산해줬다. #include using namespace std; int main(){ int n; scanf("%d", &n); if(n==1 || n==3){ printf("-1"); return 0; } int ans = 0; if(n%10 == 1){ ans+=3; n-=6; } if(n%10 == 3){ ans+=4; n-=8..

실버작 2 Hamming Distance 자체는 좀 귀찮은 개념이긴 한데 이 문제에선 굳이 Hamming Distance를 구할 필요가 없다. 그냥 각 문자 자리에서 가장 많이 등장하는 문자를 Hamming Distance의 합이 가장 작은 DNA의 문자자리에 그대로 넣어주기만 하면 된다 #include using namespace std; char arr[1234][56] = {0}; char ans[56] = {0}; int a,c,g,t; int main(){ int n,m; scanf("%d %d", &n, &m); for(int i=0; i

시험끝나고 알고리즘 재활을 시작하고 있는 코더빡입니다... 기말은 말아먹었지만 알고리즘까지 말아먹을순 없죠 ㅋㅋㄹㅃㅃ 실버로 감을 다시 잡아봅시다. 1439번 뒤집기는 이진수라는거에서 뇌절이 오면 안되는 문제였습니다. 이 문제의 핵심은 한번 뒤집을때 얼마나 효율적으로 뒤집을 수 있나 였습니다. 0에서 1로, 1에서 0으로 바뀌는 횟수를 세 줍니다 왜냐하면 뒤집는 구간을 제 맘대로 정할수 있기 때문에 1이 몇개있거나 0이 몇개있거나는 전혀 신경쓸 필요가 없기 때문입니다. 이제 다른 숫자가 등장한 횟수를 센 상태이고, xxxYYxx에서 변화횟수는 2, 가장 효율적이게 xxxxxxx로 바꾼 뒤의 변화횟수는 0임에서 착안하면 한번의 Y*k 를 x*k 로 뒤집는 연산은 변화횟수를 2만큼 줄여낼 수 있게 됩니다. ..

오늘은 세그 미는날~~ 평범한 최솟값 세그가 아니여서 좀 고생했다. www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 이 문제의 핵심은 세그트리가 반환해주는 값이 구간 내의 히스토그램 값의 최솟값 이 아니라, 히스토그램이 최솟값을 가지는 곳의 인덱스값이다. 이를 위해 세그트리를 살짝 수정해 준 뒤에, 구간에서의 최대값을 찾을때에는 분할정복을 이용해주었다. 분할을 할때는 반드시 딱 절반에서 나누는 것이 아..

프림 / 크루스칼 알고리즘을 사용하면 쉽게 해결할 수 있다. 나는 크루스칼 알고리즘을 사용했다. www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 크루스칼 알고리즘의 기본적인 구현을 묻는 문제 더보기 #include using namespace std; typedef long long int ll; struct line{ int s; int e; int w; }; vector g; int parent[12345] ..

www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 처음 보고 든 생각은 "R과 C의 범위가 작으니까 DFS등으로도 해결할 수 있을 거 같다" 였다. 구현 방법은 뭐 여러가지가 있겠지만, 나는 비트마스킹을 연습할 겸 비트마스킹으로 해결해 보기로 했다. 우선 들어오는 문자들에서 'A'만큼을 빼서 0부터 시작하는 숫자로 만들어준다음 각각 0 번째 비트, 1번째 비트, .... 등으로 각각의 비트에 방문여부를 기록해준다. 더보기 #include using na..