컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제 해결 알고리즘 알고리즘은 간단한데 그걸 구현해내는 아이디를 내기가 좀 어려웠던 문제.. 1. 점수가 높은 순서대로 (만약에 같으면 일수가 낮은 순서대로) 우선순위 큐에 정렬을 해준다. 2. 그 정렬된 큐 값에 일수를 고려한 최대값을 구해준다. 1번은 쉽지만 2번에서 막혔다. 배열을 이용해서 문제를 풀 수 있었는데 큐에서 나온 값의 일수부터 1까지의 인덱스 중 차례대로 0이면 거기에 값을 그대로 입력해주고 break를 해준다. 이 방식대..

https://www.acmicpc.net/problem/16288 16288번: Passport Control 입력은 표준입력을 사용한다. 첫 번째 줄에는 두 개의 정수 N 과 k 가 주어진다. N은 입국 승객의 수이며 k는 여권 심사 창구의 수이다. 단, 2 ≤ k ≤ N ≤ 100 이다. 그리고 두 번째 줄에는 승객이 입 www.acmicpc.net 문제 해결 알고리즘 문제가 약간 어렵게 느껴지나 생각을 조금만 해보면 풀 수 있는 쉬운 문제였다. 입력에서 주어진 수열의 연속하는 증가하는 수열의 개수가 여권 심사 창구(k)보다 많다면 불가능한 순서이고 적거나 같다면 가능한 순서이다. 예를 들어, 예제에 나온 입력을 보자 10 3 4 1 3 2 5 6 8 9 7 10 여기서 연속하는 증가하는 수열은 4..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 문제 해결 알고리즘 모든 추의 무게를 정렬 해준 후에 자기보다 왼쪽에 있는 추들의 무게의 합보다 크면 그 합에 +1인 값을 출력해주면 된다. 만약에 없다면 모든 추의 무게의 합에 +1을 해준 값을 출력해준다. 이 때, 만약 가장 무게가 가벼운 추의 무게가 1보다 크다면 1을 출력해준다. 소스 코드 #include using namespace std; int main(){ int N; cin >> N; vec..

https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 문제 해결 알고리즘 $a_1 + a_2 + a_3 = a_4$ 이렇게 구하려고하면 $O(n^4)$의 시간복잡도가 나오기 때문에 시간초과가 발생한다. 그렇기 때문에 $a_1 + a_2 = a_4 - a_3$로 두 항의 값이 같은 걸 구하기 위해 이분 탐색을 하면 $O(n^2 \log n)$으로 해야 정답을 받는다. 소스 코드 #include using..

https://www.acmicpc.net/problem/1990 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 문제 해결 알고리즘 에라토스테네스의 체를 2부터 천만까지 소수판정 후 거기서 a와 b 사이의 수 중 팰린드롬인 수를 출력해준다. 이 때, 천만 이상부터는 소수인 팰린드롬이 없으므로 천만까지만 진행해준다. 아래의 링크에 에라토스테네스의 체 알고리즘이 설명되어있다. https://kimmessi.tistory.com/152?category=871925 [알고리즘] 소수 판정법 - 에라토스..

https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 문제 해결 알고리즘 숫자를 순열로 완전탐색해주고 B보다 작고 맨 앞 숫자가 0이 아닌 수중에 가장 큰 값을 출력해준다. 소스 코드 #include using namespace std; int main(){ int cnt = 0; int result = -1; int A, B; cin >> A >> B; vector v; while(A != 0){ v.push_back(A %..

https://www.acmicpc.net/problem/9693 9693번: 시파르 N이 주어졌을 때, N!/10M이 정수가 되는 M 중 가장 큰 것을 출력하시오. www.acmicpc.net 문제 해결 알고리즘 1~N까지 모든 수를 2와 5로 나눠보면서 N!에 있는 2와 5의 개수를 찾고 둘 중 작은 수를 출력해준다. 소스 코드 #include using namespace std; int main(){ int cnt = 1; while(true){ int two_cnt = 0, five_cnt = 0; int N; cin >> N; if(N == 0) break; for(int i=1;i

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 알고리즘 문제 해결 동적계획법(다이나믹 프로그래밍)을 쓰는 문제 연속된 세 개의 계단을 밟을 수 없으므로 이차배열을 선언해준다. 연속으로 밟은 계단의 갯수를 배열로 알 수 있게 설정한다. 만약 2개의 계단을 밟았을 경우 두 칸을 넘게 한다. 반복문이 끝난 후, 마지막으로 N번째 행에서 최댓값을 구해서 출력한다. 소스 코드 #include using namespace std; int main(){ int N; ..