0과 1의 쉼터

풀이 9등분을 하고, n/3만큼 좌표를 (x, y) 증가시켜 Divide and Conquer 하면 된다. N만큼의 종이가 모두 같을 때, 탐색을 중단해야 하므로 중단 조건을 함수로 만들어 풀이했다. 소스코드 #include int paper[2187][2187], I[3]; int all_same_paper(int x, int y, int n){ int temp = paper[x][y]; for (int i = x; i < x+n; i++) for (int j = y; j < y+n; j++) if (paper[i][j] != temp) return 0; return 1; } void division(int x, int y, int n){ if (all_same_paper(x, y, n)) I[pape..

풀이 Dynamic Programming의 Memorization 방식으로 풀이했다. (S~E) 구간이 팰린드롬인지 알기 위해서는 (S+1 ~ E-1), (S+2 ~ E-2), ... (X, X+1) or (X, X)구간의 수들이 팰린드롬인지 알아내는 과정을 반복해야한다. 길이가 3이상일 때, 요소가 홀수개인 팰린드롬은 최종적으로 길이가 1인 팰린드롬의 여부에 따라, 요소가 짝수개인 팰린드롬은 최종적으로 길이가 2인 팰린드롬의 여부에 따라 결정되기 때문에 다음과 같이 나누었다. 입력을 받을 때 길이가 1, 2인 펠림드롬을 확인하고, for (int i = 1; i 1 && arr[i] == arr[i-1]) dp[i-1][i] = 1; } 입력이 끝난 후 길이가 3 이상인 팰린드롬을 구했다. for (i..

소스코드 #include int N; const char *str[7] = { "\"재귀함수가 뭔가요?\"", "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.", "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.", "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"", "\"재귀함수가 뭔가요?\"", "\"재귀함수는 자기 자신을 호출하는 함수라네\"", "라고 답변하였지." }; void message(int n){ for (int i = 0; i < 4; i++){ for (int j = 1; j < n; j++) printf("____"); puts(str[i]); } if (n..

소스코드 #include int main(){ char ch; while((ch=getchar()) != EOF) putchar(ch); } 출처 11719번: 그대로 출력하기 2 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 주어질 수도 있고, 각 줄의 앞 뒤에 공백이 www.acmicpc.net

풀이 0의 개수는 2와 5의 곱의 쌍을 통해 알 수 있다. (2*5 = 10, 15 * 2 = 30) 하지만 팩토리얼이기 때문에 2의 배수는 무수히 많으므로, 5의 제곱수의 개수만 알아내면 된다. N은 최대 500이하 이므로, 125, 25, 5로 나누어 떨어지는 경우만 해당한다. 소스코드 #include int main(){ int N, cnt = 0; scanf("%d",&N); for(int i = 1 ; i

풀이 가치가 n인 동전으로 k를 만드는 경우의 수는 k-n을 만드는 경우의 수와 같다. (단, k-n = 0의 경우의 수는 1로 설정) ex) n = 2, k 1 2 3 4 5 6 7 경우의 수 0 1 0 1 0 1 0 가치가 n1, n2인 동전으로 k를 만드는 경우의 수는 "k-n을 만드는 경우의 수 + n1으로 k를 만드는 경우의 수"와 같다. ex) n1 = 1, n2 = 2 k 1 2 3 4 5 6 7 8 9 10 n1 1 1 1 1 1 1 1 1 1 1 n2 2 2 3 3 4 4 5 5 6 이를 코드로 표현하면 다음과 같다. for (int i = 0; i < n; i++) for (int j = coin[i]; j

풀이 가치가 가장 큰 동전부터 K이하일 때 하나씩 빼주고 횟수를 세주면 된다. 소스코드 #include int main(){ int N, K; scanf("%d %d", &N, &K); int coin[N]; for (int i = 0; i < N; i++) scanf("%d", &coin[i]); int cnt = 0, idx = N-1; while (K) if (K < coin[idx]) idx--; else { K -= coin[idx]; cnt++; } printf("%d", cnt); } 출처 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1..

풀이 별로 만들어지는 삼각형의 높이와 너비는 각각 2^(N) -1, 2^(N+1) -3이다. 다음은 N=3일 때의 예제이다. 빨간 사각형은 mark_star(x, y, n)을 Recursive Call할 때 해당하는 영영이고, (x, y)는 맨 좌측상단이며, N=1때 는 (x, y)와 영역이 일치하므로 별을 찍어주고 함수를 종료한다. 연두색과 하늘색 공간의 별은 다음과 같이 찍었다. for (int i = 0; i < width; i++) arr[x+(n%2 ? height-1 : 0)][y+i] = '*'; // 연두색 for (int i = 0; i < height; i++){ if (n%2) arr[x+i][y+width/2-i] = arr[x+i][y+width/2+i] = '*'; // 하늘색 ..

풀이 "백준 11726, 2×n 타일링" 문제와 비슷하다. 심지어 정답도.. 2x1 타일을 1, 1x2 타일을 2, 2x2 타일을 T라고 가정할 때 다음과 같이 나타낼 수 있다. N 타일 dp[1] 2 11 2, T 3 3 111 12,1T 21,2T 5 4 1111 112,11T 121,1T1 211,T11 22,TT 2T,T2 11 5 11111 1112,111T 1121,11T1 1211,1T11 2111,T111 122,1TT 212,T1T 221,TT1 12T,1T2 21T,T12 2T1,T21 21 6 " 43 7 " 85 8 " 171 N번째 방법의 수는 "2 * (N-2번째 방법의 수) + (N-1번째 방법의 수)" 와 같음을 알 수 있다. 소스코드 #include #define MOD 1..

풀이 입력받은 좌표들을 오름차순으로 정렬하고, 중복을 제거했을 때, 각 요소들이 몇 번째인지 출력하는 문제다. 입력받은 수들을 두 벡터에 저장하고, v2는 오름차순으로 정렬 후, 중복을 제거했다. 중복된 수가 제거된 v2에서 lower_bound()를 사용하면, 원하는 결과를 얻을 수 있다. 소스코드 #include #include #include using namespace std; int main(){ int N, temp; scanf("%d", &N); vector v1(N), v2(N); for (int i = 0; i < N; i++){ scanf("%d", &temp); v1[i] = v2[i] = temp; } sort(v2.begin(), v2.end()); v2.resize(unique(..