JJ_blog

빙산의 덩어리 개수를 파악하기 위해서 자신 있게 dfs를 이용하여 문제를 풀었지만 결과는 시간초과 ㅜㅜ (dfs 안써..) □ 망한 코드.. ㅎ (잘못 나올 수 도 있어요!) vector input2573(301,vector(301,0)); vector modSea2573(301,vector(301,0)); vector check2573(301,vector(301,false)); int N2573, M2573; bool dfs2573(int x, int y, bool check){ if(x M2573) return false; if(check){ if(modSea2573[x][y] == 0 && input2573[x][y] != 0 && !check2573[x][y]){ int countSea = 0; ..

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

문제를 해결하는 아이디어는 가장 넓은 안전 영역을 구하는 것이므로 벽을 설치한 후 바이러스를 퍼트려보고 완료된 그래프를 탐색하여 안전영역의 개수를 출력하면 되는 문제이다. 바이러스를 퍼트리고 안전영역을 찾는건 정말 쉬운 문제인데.. 이놈의 벽..! 해당 문제를 처음 딱 읽고 이해는 갔지만 이 벽이 문제였다. 벽 3개를 어떻게 배치를 할 것인가.. 처음에 반복문을 이용하여 배치를 해보았지만 내 구현 능력이 부족한지 계속해서 실패하였다. ㅜㅜ 결국.. 인터넷의 힘을 빌릴 수 밖에..ㅠ 재귀를 이용하여 벽을 세우는데 약간 신기했다. (새로운 패턴 익히는 중) □ 소스코드 #include using namespace std; vector inputOrginal14502(9,vector(9,0)); vector ..