컴공과컴맹효묘의블로그

백준을 풀던 중 조합을 이용하는 문제가 나왔다. 코테에서도 조합문제가 빈번히 등장한다고 하니 조합을 구현하는 연습을 할 필요가 있다. https://www.acmicpc.net/problem/15686 [15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net](https://www.acmicpc.net/problem/15686) bool next(std::vector& comb, int num) { if (comb.empty()) return false; int back = comb.back();..

제출자: 61 정답자: 60 정답률: 98.4% 문제: https://www.acmicpc.net/problem/15999 15999번: 뒤집기 첫 줄에 격자의 초기 상태로 가능한 경우의 수를 1,000,000,007(109 + 7)로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 문제를 조금만 관찰하면 금방 패턴을 파악할 수 있는 문제입니다. 현재 상태가 주어졌을 때 초기 상태로 가능한 경우를 생각해보면 바로 풀리는 문제입니다. 예를 들어 현재 상태가 WB였을 때, 초기상태로 가능한 것은 WW, BB, WB, BW중 하나 이상일 것입니다. WW는 WB가 될 수 없으므로 초기상태가 불가능합니다. BB또한 WB가 될 수 없습니다. WB는 WB에서 0번 건들면 현재 상태가 됩니다. BW는 WB가..

https://www.acmicpc.net/category/detail/1915 카카오 코드 페스티벌 2018 www.acmicpc.net

백준 알고리즘[9694] 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 문제 한신이는 젊고, 똑똑하고 매우 유명한 정치인이다. 그럼에도 그는 여전히 자신의 성공을 위해서도 인간관계는 중요한 것이라고 믿고 있다. 다음 달에 열릴 국회의원선거에서 한신이는 자신의 당이 반드시 이기길 희망한다. 그러기 위해서 최고의원의 지지가 필요하다. 이 최고의원의 지지를 받기위해 한신이는 전략을 세웠다. 그는 그 최고의원을 직접적으로 만날 수 없다면 그를 알고 있는 인맥을 이용하여 만날 것이다. 이것을 위해서 우선 정치인들의 친밀도를 조사하였는데 친밀도를 다음 4단계로 나누어서 기록해놓았다. 최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4] [두 사람의 관계는 이 4가지 경우중 반드시 해당되며, 적(en..

문제 사이트: https://www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 어떤 자연수 N을 2의 멱수의 합으로 나타내는 경우의 수를 구하는 프로그램을 작성하시오. 2의 멱수라는 것은, 2^k으로 표현되는 자연수를 의미한다. 예를 들어 7을 2의 멱수의 합으로 나타내는 경우의 수는 다음의 여섯 가지가 있다. 1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+2+2 1+1+1+4 1+2+2+2 1+2+4 입력 첫째 줄에 N(1≤N≤1,000,000)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로..

문제 사이트 : https://www.acmicpc.net/problem/16112 문제 메이플스토리 뉴비 키파가 드디어 레벨 200을 달성하고 5차 전직이라는 시스템을 이용해 캐릭터를 더욱 강력하게 만들려고 합니다. 5차 전직을 하려면 먼저 퀘스트를 통해 아케인스톤이라는 아이템을 받아야 합니다. 아케인스톤을 활성화시키면 캐릭터가 얻는 경험치를 아케인스톤에 모을 수 있습니다. 5차 전직을 하기 위해서는 총 n개의 퀘스트를 진행해서 n개의 아케인스톤을 받아야 하며, 각각의 아케인스톤에 5억 이상의 경험치를 모으면 5차 전직을 진행할 수 있는 자격이 주어집니다. i번째 퀘스트를 진행하면 ai의 경험치와 i번째 아케인스톤이 주어집니다. 퀘스트로 얻는 경험치도 사냥으로 얻는 것과 똑같은 경험치이기 때문에, i번..

문제 사이트 : https://www.acmicpc.net/problem/18825 쭉! 쭉 쭉쭉! 쭉! 쭉 쭉쭉! 언제까지 어깨춤을 추게 할 거야! 내 어깨를 봐! 탈골됐잖아! 이 문제의 데이터는 문제를 맞은 사람의 수에 따라 바뀝니다. 제출된 소스 코드 이전 제출 중 맞았습니다!!를 받은 사람의 수를 n이라 합시다. n+2를 나누는 가장 작은 소수를 p라 하고, p 이하의 소수의 개수를 k라 합시다. 이때 999+k번 문제를 푸는 소스 코드를 제출하세요. 즉, 만일 13명이 맞았다면 15를 나누는 가장 작은 소수는 3이고 3 이하의 소수의 개수는 2개이므로, 1001번 문제인 A-B을 푸는 코드를 제출하면 됩니다. 만일 (999+k)번 문제가 ICPC 스타일 문제가 아니면 채점하지 않고 맞았습니다!!..

문제 사이트 : https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민 www.acmicpc.net 문제 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다...

문제 사이트 : https://www.acmicpc.net/problem/11052 생각의 시퀀스 각각 다르거나 같은 개수의 카드가 들어있는 카드팩을 샀을 때, 모든 카드의 합이 N이 되는 경우의 최대값을 구하라. 처음 든 생각은 기계적으로 튀어나온 dp[i] = max(arr[i], dp[i-1]+arr[0]) arr이 카드팩 비용이고 dp는 i-1개의 카드를 산 경우 최대 비용. 그러므로 dp[0] = arr[0] 하지만 위 코드는 동작하지 않았고 나는 멍청했다.. 위 점화식에서 dp[i-j]+arr[j-1]를 쓴다면 시간 오버가 될거라 생각함. 그래서 멀리 돌아돌아 카드팩을 사는 모든 경우의 수를 재귀식으로 돌리고, 카드의 합이 N이 될때마다 max인지 구하는 식으로 생각해봤는데 이게 더 오래걸릴거..

문제 사이트 : https://www.acmicpc.net/problem/11729 생각의 시퀀스 및 풀이 최근 알고리즘을 제대로 공부해야겠다는 생각에 일명 "종만북"이라 불리는 "프로그래밍 대회에서배우는 알고리즘 문제해결 전략"을 구입했다. 종만북은 나에게 너무 어려운 책이였다. 종만북에 실려있는 예제는 난이도가 상당하게 느껴졌고, 풀이를 보면 어떻게 이런 생각을 했을까? 하게 만드는 책이였다. 암튼 이 책을 200페이지까지 보고 쉬어가는 느낌으로 백준 알고리즘 [분할 정복]파트를 풀기로 했다. 난 이미 종만북 200페이지까지 봤으니 분할 정복에 대해선 어느정도 아는 상황이였다. 처음엔 감도 안잡혔다. 일단 히노이 탑을 옮기는 상상부터 했다. 첫 번째 장대를 세 번째 장대로 옮겨야 하니까... 판이 1..