JJ_blog

3 번째 예제를 보지 못하고 신나는 마음에 문제를 재귀로 쉽게 풀어내서 이게 실버문제라고..?라는 의문이 드는 순간 무려 4천조나 되는 숫자가 나와서 매우 당황..;; 처음에 신나는 마음에 푼 코드.. 는 정말 단순하게 있는 그대로 구현한 것 같다. 끙끙 헤매다가 결국 인터넷의 힘을 빌릴 수밖에..ㅜ 숫자가 매우 커서 재귀를 무작정 돌리는 경우 시간초과가 나는 것은 무조건이다. 따라서 DP를 이용하여 풀어야 하는데 솔직히 막막하다. 햄버거 재료 개수랑 패티 개수를 저장할 배열을 생성한 후 미리 개수를 저장해 놓는다. 그리고 우리가 구하고 싶은 것은 패티! 의 개수가 중요하니까 모든 코드는 패티의 개수에 맞춰서 짠다. 우선 전체 코드 공개! #include #define fast ios::sync_with..

이 문제는 N과 M 시리즈 문제를 풀었다면 정말 눈감고(?)도 풀 수 있다. #include using namespace std; vector arr10974; vector check10974(9,0); void backback10974(int N, int count){ if(N == count){ for(int i=0;i

문제를 읽고 예제를 봤을 때 왜 62가 나오는지 몰랐다.(하핳) 그래서 문제에서 알려준 식을 가지고 코드로 변환하여 작성했더니 정말 62가 나와서 놀랬다.ㅎ #include using namespace std; int N10819; int maxNum = -INT_MAX; vector input10819; vector check10819(9,false); vector tmp10819; void backback10819(int count){ if(count == N10819){ int sum = 0; for(int i=0; iN10819; for(int i=0;i>a; input10819.push_back(a); } backback10819(0); cout

이 문제가 왜 골드 4인지 잘 모르겠다..ㅋ 빈칸에 전부 다 대입을 한 후 반복문을 돌리면서 확인하는 경우의 수는 너무 많이 나오고 시간초과가 발생할 확률이 매우 높다. 따라서 빈칸에 적당한 값을 넣기 전에 같은 행, 열, 블록을 검사한 후 같은 숫자가 없는 경우 대입하는 방법으로 문제를 해결해야 한다. #include using namespace std; vector input2580(10,vector(10,0)); vector zeroPos2580; bool complete2580 = false; bool checkValidSudo(int x, int y){ // 세로 가로줄 검사 for(int i=1; i

정말 순수하게 알파벳이 지나온 길을 저장한 뒤에 한번 재귀가 돌때마다 반복문을 돌며 저장된 알파벳을 탐색하는 방식으로 풀었다. 그런데 바로 시간초과 ㅜㅜ □ 해결은 됐지만 시간초과가 된 코드 #include using namespace std; int R1987, C1987; vector input1987(21,vector(21,NULL)); vector check1987(21,vector(21,false)); vector doneAlpha1987; int result1987 = 0; bool checkAlphabet1987(char now, int count){ for(int i=0;iR1987>>C1987; for(int i=1;ia; input1987[i][j] = a; } } backback198..

부분 수열을 더하면서 입력한 값과 같게 되는 경우의 수를 구하는 문제인데 백트래킹의 기본적인 문제인데 출력값이 자꾸 하나씩 더 나와서 당황했다. 원인은 원하는 값이 0인 경우 count값이 0부터 시작하여 값이 한개 더 추가된다는 것 이였다. 그래서 조건문에서 count가 1부터 통과되록 조건을 추가 시켜서 해결하였다. #include using namespace std; vector input1182(21,0); vector check1182(21,false); int N1182,S1182; int result1182 = 0; void backback1182(int count, int pos, int sum){ if(sum == S1182 && count > 0) result1182 ++; if( co..

약간의 백트래킹 방법에서 살짝만 바뀐 방법으로 문제를 해결할 수 있다. 일반적으로라면 count를 증가시켜 확인 후 return; 하지만 해당 문제는 모음 개수와 자음 개수를 따로 계산하여 가져가야한다. 나머지는 백트래킹 하듯이 하면 해결할 수 있다. #include using namespace std; int L1759, C1759; vector input1759; vector result1759; vector check1759(16,false); char vowelList1759[] = {'a','e','i','o','u'}; void backback1759(int pos, int vowelCount, int conCount){ if(vowelCount + conCount == L1759 and vo..

주어진 오름차순 수열을 가지고 6개의 숫자를 뽑아 출력하는 문제이다. 백트래킹을 활용하면 문제를 쉽게 해결할 수 있다. #include using namespace std; vector input6603; vector check6603(14,false); vector result6603; int K6603; void backback6603(int count, int pos){ if(count == 6){ for(auto& i: result6603){ cout

종이의 개수 문제는 이전에 블로그에 올렸던 색종이 만들기 문제와 완전 똑같다. #include #define MAXARANGE 2200 using namespace std; vector input1780(MAXARANGE,vector(MAXARANGE,0)); int minusOneCount = 0; int oneCount = 0; int zeroCount = 0; void recursive1780(int N, int x, int y){ if(N==1){ if(input1780[x][y] == 1) oneCount++; else if(input1780[x][y] == 0) zeroCount++; else if(input1780[x][y] == -1) minusOneCount++; return; } boo..

이전에 블로그에 올렸던 문제 색종이 만들기 문제와 매우 유사한 문제지만 출력방식이 다르다. 처음에 문제를 봤을 때 이해가 정말 안됐었다.. 색종이 만들기 문제는 파란색, 하얀색 종이의 개수를 구하는 문제라면 해당 문제는 1과 0이 정사각형 모양으로 반복되는 구간이 있다면 1로 압축하는 문제이다. 예를들어 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 이와 같이 주어진 경우 (10(1100)1)로 출력할 수 있다. 4등분을 먼저 하면 아래와 같이 볼 수 있다. 1번 2번 3번 4번 1번의 경우 모두 같은 숫자 1로 구성되어 있으므로 1로 압축을 할 수 있다. 2번의 경우에도 0으로 모두 구성되어 있으므로 0으로 압축할 수 있다. 3번의 경우 1과 0이 섞여 있으므로 다시 한번 재귀를 통해 4등분..