problem solving (93) 썸네일형 리스트형 2011번: 암호코드 현재 숫자와 이전숫자가 11 ~ 26일 경우 현재 숫자와 이전 숫자를 따로 봤을 때 가능한 이전까지의 방법 수와, 하나의 봤을 때 가능한 이전이전까지의 방법 수를 더해서 답을 구했다. 그리고! 10으로 나누어 떨어질 때 가능한 경우는 1이므로 적절한 예외처리가 필요하다. 첫째 자리가 0일 경우에도 코드 조합을 만들 수 없으므로 적절한 처리를 해주자. #include #include int main(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::string val; std::cin >> val; int dp[5001] = { 0 }; dp[0] = 1; dp[1] = dp[0]; int check = (val[0] - '0'.. [하노이 탑]재귀 재귀를 약간 알고 있는 정도였는데 하노이 탑 문제를 보고 상당히 당황했다. 그래서 잘 알고자 정보를 찾아봤는데 아래 사이트에서 재귀에 대해 조금 더 이해할 수 있었다. https://www.acmicpc.net/board/view/19958 글 읽기 - 하노이탑 재귀함수 쉽게 이해하는 방법 있나요? 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 10844번: 쉬운 계단 수 dp문제다. 0, 9 는 퍼져나갈 수 있는 1과 8밖에 못받고 나머지는 자신의 수 -1, +1인 수의 개수를 받을 수 있다는 것을 이용했다. 처음에 0이 오면 안되기 때문에 마지막에서부터 연산을 진행해 최종적으로 1~9로 시작할 수 있는 계단 수를 더해서 답을 구한다. (아래의 식을 이용하면 sum이 아닌 dp만을 나누어 준다는 것에 주의! sum += dp[len-1][k] % 1000000000;) #include int main(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int len; std::cin >> len; long long dp[101][10] = { 0 }; for(int i = 0; i 10815번: 숫자 카드 카드의 개수가 많기 때문에 순차적으로 탐색한다면 시간초과가 난다. 이분 탐색을 이용해 시간복잡도를 줄이면 정답을 얻을 수 있다. #include #include int user1Card[500001] = { 0 }; int user1Count, user2Count; int search(int val, int front, int end) { int mid = (front + end) / 2; // std::cout 10610번: 30 아래의 블로그에서 배수판정법에 대한 정보를 참고해서 코드를 작성했다. https://freshrimpsushi.tistory.com/21 3의 배수판정법과 9의 배수판정법의 증명 각 자리 숫자를 모두 더해 3의 배수면 3의 배수, 9의 배수면 9의 배수 예를 들어 8142는 8142=3*2714로 3의 배수고, 실제로 8+1+4+2=15는 3의 배수다. 1945125는 1945125=9*216125로 9의 배수고, 실제로 1+9+4+5+1.. freshrimpsushi.tistory.com #include #include #include int main(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::string val; s.. 9613번: GCD 합 GCD는 최대 공약수를 의미한다. 유클리드 호제법을 이용해 간단하게 문제를 풀 수 있다. (합의 크기가 int범위를 넘어갈 수 있는 것에 주의) #include void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } int main(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int testCase; std::cin >> testCase; int len; int val[101] = { 0 }; for(int i = 0; i > len; for(int j = 0; j > val[j]; } long long sum = 0; for(int k = 0; k 9446번: 텀 프로젝트 보기보다 까다로운 문제다. (너무 지저분해서 내 코드를 완벽히 설명하기가 힘들 거 같다...) 처음에는 쌍을 찾기위해서 check 배열을 선언해서 각 testCase마다 초기화했었다. 하지만 시간이 한참 초과되는 걸 보고 check 배열을 초기화하는 대신 각 testCase마다 특정 수를 이용해서 하나의 check 배열을 재활용할 수 있도록 했다. DFS 함수에서 정답을 찾으면 skip 배열에 해당 testCase에 해당하는 특정 수를 부여해주고 이후 탐색한 순서 역순으로 되돌아가면서 해당하는 수의 skip 배열에 testCase에 해당하는 특정 수를 부여하고 sum을 +1 한다. DFS함수가 종료되면 쌍을 갖춘 학생들의 합인 sum과 총 학생 수인 len의 차이를 출력한다. #include #inclu.. 9019번: DSLR 시간초과를 해결하는게 상당히 까다로운 문제다. string 사용을 최소화하여 BFS로 탐색한다면 정답에 도달할 수 있을 거다. #include #include #include #include #include int check[10000] = { 0 }; int main(void) { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int testCase; std::cin >> testCase; int val, reach; std::queue mQ; for (int i = 0; i > val >> reach; while (!mQ.empty()) { mQ.pop(); } memset(check, false, sizeof(check)); mQ.push({ "", v.. 이전 1 ··· 6 7 8 9 10 11 12 다음