알고리즘 문제풀이/백준134 [백준 20310] 타노스 www.acmicpc.net/problem/20310 20310번: 타노스 어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다. 갑자기 심술이 난 타노스는 $S$를 구성하는 문자 www.acmicpc.net 문자열 알고리즘 문제 문자열 내의 순서는 고정이라는 전제하에 풀어야 한다. 아니면 25점 ㅠ 0과 1 절반씩을 날린다고 했으므로 사전순으로 빠른 것을 구하기위해 0은 뒤에 절반을, 1은 앞에 절반을 날린다.ㅏ 덱을 사용해도 되지만 배열에서 해결하기 위해 머지소트에서 사용하는 로직을 사용했다. #include #include #include using namespace std; char s[501].. 2020. 12. 31. [백준 17392] 우울한 방학 www.acmicpc.net/problem/17392 17392번: 우울한 방학 1일, 5일, 8일에 약속을 순서대로 배치하면, 4일과 10일에 각각 1만큼의 우울함을 느끼게 되어, 총 2만큼의 우울함을 느끼게 된다. 이보다 덜 우울함을 느끼게 만드는 방법은 존재하지 않는다. www.acmicpc.net 그리디 알고리즘 사용 식을 사용하는 문제이다. 우울함의 값은 기분이 음수일때 제곱을 해서 나타내므로 음수인 날이 적어야한다. 음수인 날을 커버할 수 있는게 약속의 기대행복값이다. 약속의 기대 행복값은 약속 당일 h 라면 하루가 지날수록 h-1 h-2..0까지 줄어든다. -> 그럼 약속 하나를 잡았을 때 기분이 0이상인 날은 h+1이란 의미다. 따라서 입력값을 받으면서 h+1을 sum에 더해준다. 이 su.. 2020. 12. 31. [백준 16112] 5차 전직 www.acmicpc.net/problem/16112 16112번: 5차 전직 메이플스토리 뉴비 키파가 드디어 레벨 200을 달성하고 5차 전직이라는 시스템을 이용해 캐릭터를 더욱 강력하게 만들려고 합니다. 5차 전직을 하려면 먼저 퀘스트를 통해 아케인스톤이라는 아 www.acmicpc.net 그리디 문제 예시 두 세가지 정도 확인하면 식을 세울 수 있다. 주의해야할 건 롱롱으로 인한 오버 플로우 처리.. 식 세우기 전체 n개의 퀘스트와 k개의 돌맹이를 활성화시킨다. A1 A2 A3 .... AN S1 S2 .. SK S1이 활성화된 이후 쌓이는 경험치는 A2 + A3 + ... + An S2에 쌓이는 경험치는 A3 + A4 + .. An Sk에 쌓이는 경험치는 Ak+1 .. + An 일 것이다. 정리하.. 2020. 12. 31. [백준 11501] 주식 www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 그리디 알고리즘을 사용한다. 문제 예시에서도 잠깐 비춰지지만 수열 전체가 오름차순이면 사서 파는게 이득이고 수열 전체가 내림차순이면 존버가 이득이다. 수열 전체가 내림차순인지 오름차순인지 앞에서 부터 순열을 돌아선 알 수 없다. 따라서 맨 뒤부터 숫자를 확인한다. 순열이 오름차순일수도 내림차순일수도 오르락 내리락 할수도 있다. 아마 대부분 오르락 내리락 할 것이다. 그렇다면 뒤에서 숫자를 확인하며 .. 2020. 12. 31. 이전 1 ··· 10 11 12 13 14 15 16 ··· 34 다음
