JJ_blog

투포인터를 이용하여 연속한 숫자의 합이 입력 값 N과 같아지는 경우의 수를 찾는 문제이다. first, second 두 변수를 이용하여 sum N 경우 first를 증가시켰다. #include using namespace std; void num2018(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin>>N; int count = 0; int first = 1; int second = 1; int sum = 0; while(1){ if(sum == N) count++; if(first == N ) break; if(sum N){ sum -= first; first++; } } if(N==1) 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등분..

해당 문제는 주어진 그래프에서 파란색 종이와 하얀색 종이의 개수를 구하는 문제이다. 예시로 주어진 그래프를 보다보면 패턴이 보이는데 처럼 숫자가 다른경우 계속 쪼개지면서 종이가 나누어 지게 된다. 따라서 재귀함수를 이용해서 개수를 구하면 된다. 처럼 N을 먼저 탐색해보고 숫자가 다른게 하나라도 있다면 반으로 줄이는 방식으로 문제를 해결하면 된다. #include using namespace std; vector input2630(130,vector(130,0)); int blueCount2630 = 0; int whiteCount2630 = 0; void divide2630(int N, int x, int y){ if(N==1){ if(input2630[x][y] == 1) blueCount2630++;..

재귀함수에 약간의 감을 잡기 위한 문제이다. 재귀를 쓰기전에는 약간의 패턴을 분석하면 쉽게 풀 수 있다. #include using namespace std; void recursive17478(int N, int start){ for(int i=0;i

배낭 관련된 문제들을 풀때 2차원 배열에 어떤 값을 넣어야 풀 수 있는지 아직 감이 잡히지 않는 것 같다. 배낭 유형 문제들을 풀면서 감을 익혀야 할 것 같다. 문제 - 1 페이지 www.acmicpc.net 이번 문제도 삽질을 좀 많이 했다.. 2차원 배열에서 행: 입력 횟수, 열: 비용으로 생각하고 풀면 되지만 열에 해당하는 최댓값은 입력받은 모든 비용의 합으로 해야한다. #include #define BYTE 1 #define COST 0 using namespace std; void app7579(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N,M; cin>>N>>M; vector App(N+1); int dp[N+1][1..

배낭 알고리즘은 DP의 대표적인 문제라고 한다. (사실 처음 봄.. ㅎ) 문제를 풀고 보니 앞선 문제에서 사용했던 LCS 푸는 방법과 유사했다. 예시를 통해서 알아보자 (백준 예제를 살짝 변형한 예제이다) 다음과 같이 입력을 받았다고 하자 index는 arr 배열에서의 index를 의미한다 여기서 weight = 0, value = 1이다. ex) arr [1][weight] = 6, arr [1][value] = 13 LCS 알고리즘에서 DP table에 값을 저장할 때 해당 값의 유무가 아닌 이전 값을 고려하여 정보를 저장했다. (먼저 혼자서 끄적여 본 표..) 위 표에서 자세하게 봐야할 부분은 (n=3, k=7)인 부분이다. arr에서 (n>n>>k; int arr[n+1][2]; int dp[n+..

LCS 2와 다르게 이번에는 3개의 문자열을 받아서 처리하는 문제이다. LCS 2에서 두개의 문자열을 비교할 때 반복문 2번을 돌렸다면 이번에는 3번을 돌리면 된다. □ 소스 코드 void LCS1958(){ ios::sync_with_stdio(false); cin.tie(NULL); string arr1, arr2, arr3; cin >> arr1 >> arr2 >> arr3; int LCS[101][101][101] = {0}; for(int i=0;i

2중 반복문을 돌려서 해당 문자열까지 겹치는 횟수를 2차원 배열에 기록하는 방법으로 문제를 해결했다. 여기서 중요한 것은 2차원 배열에 기록을 할 때 문자 하나하나를 비교해서 기록하는 것이 아닌 문자열과 비교해서 기록해야 한다는 것이다. 예를 들어 왼쪽 문자열(ACAYKP)에서 부분 문자열 A와 위쪽 문자열(CAPCAK)에서 부분문자열 C와 비교한다면 A와 C는 겹치는 부분이 없으므로 0이 된다. 그다음 왼쪽 문자열(ACAYKP)에서 부분 문자열 AC와 위쪽 문자열(CAPCAK)에서 부분문자열 C를 비교해 보면 AC와 C는 겹치는 문자가 C 하나가 있다. 따라서 해당 부분에 1을 기록한다. 그다음 왼쪽 문자열(ACAYKP)에서 부분 문자열 ACA와 위쪽 문자열(CAPCAK)에서 부분문자열 C를 비교해 보..

전깃줄 문제를 처음 접했을 때 앞에 가장 긴 시리즈 문제들을 해결을 한 상태라서 되게 쉽게 느껴졌다. 그림을 본 순간 든 생각은 A와 연결된 B애들을 순서대로 적어보자! 였다. 적자마자 수열이 떠올랐다. ㅋㅋ 해당 수열을 가지고 가장 긴 증가하는 수열을 찾고 전체 길이에서 빼주면 답이 나온다. ㅎㅎ 가장 긴 시리즈에서 유용하게 사용했던 Dp + 이진탐색을 활용해서 문제를 해결했다. 전깃줄 2 길이를 구하는 건 쉬운데 또 부분 수열의 요소들을 찾으랜다. 이것 역시 가장 긴 수열 시리즈에서 했던 역추적 방법을 사용하면 풀 수 있다. 역추적을 하고 나면 위에서 작성했던 가장 긴 부분 수열은 {1, 4, 6, 7, 10}이 나오게 된다. 그러면 {8, 2, 9, 1, 4, 6, 7, 10}에서 가장 긴 부분 수..