알고리즘
-
11365번 : !밀비 급일알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 14. 15:01
매우 귀찮은 문제죠. 이제 stdio.h에서 gets도 못쓰는거 같아서 더욱 풀기 어려워졌습니다.우선 gets를 fgets형태로 바꿔볼까요?fgets(arr, 500, stdin);자 이러면 개행문자도 받아버린답니다~ 출력할 때 개행문자를 씹어줘야겠죠?if (arr[len - i - 1] == '\n') continue;개행문자를 받아버려서 strcmp도 못씁니다. 그럼 END는 어떻게 할까요?if (arr[0] == 'E' && arr[1] == 'N' && arr[2] == 'D') break;하나하나 다 해주면 되죠! 그럼 이걸 코드로 모아볼까요? #include #include char arr[501];int main() {while (1) {for (int i = 0; i < 501; ++i) ..
-
2675번 : 문자열 반복알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 14. 14:34
해당 문자열을 각 글자마다 N번 반복하여 출력하는 간단한 프로그램입니다.유의할 점은 for ( int i=0 ; i < strlen(arr) ; ++i )가 시간초과의 주요 원인이기 때문에int len=strlen(arr);for ( int i=0 ; i < len ; ++i )이런 식으로 코딩합시다. #include #include int main() {int T;scanf("%d", &T);while (T--) {int N;scanf("%d", &N);char arr[21];memset(arr, 0, 20);scanf("%s", arr);int len = strlen(arr);for (int i = 0; i < len; ++i) {for (int j = 0; j < N; ++j) {printf("%c..
-
11048번 : 이동하기알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 8. 13:18
모든 수를 담을 공간이 1000x1000이고, 이는 이차원 배열로 충분히 들어가기 때문에 dp도 1000x1000으로 정의해도 괜찮다. 방법은 간단하다. 배열을 arr에 모두 받은 다음 dp[i][j]가 dp[i-1][j] , dp[i][j-1] , dp[i-1][j-1] 중 가장 큰 값 + arr[i][j]으로 쌓아주면 된다. #include int dp[1001][1001], arr[1001][1001], N, M;int MAX3(int a, int b, int c) {return a > (b > c ? b : c) ? a : (b > c ? b : c);}int main() {scanf("%d %d", &N, &M);for (int i = 1; i
-
2294번 : 동전2알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 7. 00:53
문제를 보면 숨이 막힙니다. 어떻게 풀지 감도 안오는 경우가 많죠. 생각을 조금 다르게 하면 오히려 쉬운 문제가 될 수 있습니다.동전의 가치에 초점을 두지 않고, 동전의 개수와 가치의 합에 초점을 두는 것이죠.우선 변수들의 범위부터 파악을 해봅시다.동전의 가치는 총 100개까지 입력받을 수 있습니다.동전의 가치는 100000보다 작거나 같은 수 입니다.가치의 합은 최대 1부터 10000까지입니다. 그러면 이제 dp테이블을 설계해봅시다.dp[i]가 무엇을 뜻해야 값이 쌓일 수 있을까요? 굳이 dp[i-1]과 dp[i]가 관련될 필요는 없습니다.네. 많은 풀이가 있겠지만 저는 dp[i]=가치의 합이 i원이 될 때의 최소 동전 개수 로 정의하였습니다.이때 가치의 합은 최대 100000이 될 수 있으니 dp[1..
-
2167번 : 2차원 배열의 합알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 6. 15:47
부분사각형을 구하는 문제다. 이 문제의 핵심은 "사각형을 어떻게 만들 것인가"이다. 위 사각형을 보자. 왼쪽 아래 꼭지점이 원점이라고 할 때, 1번 사각형의 넓이는 어떻게 나타낼 수 있을까?그렇다. (전체 사각형의 넓이)에서 (2번사각형+4번사각형)을 빼고 (3번사각형 + 4번사각형)을 뺀 다음 (4번사각형)을 더해주면 된다.왜 이런 방법을 쓸까?그 이유는 넓이를 표현하기가 쉬워서 그렇다. 이 그림을 보면 ((0,0)은 4번사각형의 왼쪽 아래 꼭짓점을 나타냄) 1) (전체 사각형의 넓이)는 (0,0) 에서 (x,y)까지의 넓이2) (2번사각형 + 4번사각형)은 (0,0)에서 (i, y)까지의 넓이3) (3번사각형 + 4번사각형)은 (0,0)에서 (x, j)까지의 넓이4) (4번사각형)은 (0.0) 에서 ..
-
9465번 : 스티커알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 6. 14:18
까다롭게 보이지만, 실제로는 전혀 까다롭지 않다.행은 2행으로 고정되어있고 열이 유동적이니 1열부터 n열까지 dp를 채워나가면 될 것 같다.각 열마나 선택지가 총 3개가 있다. 아무것도 선택하지 않거나, 1행을 선택하거나 2행을 선택하는 것이다. i번째 열에서 아무것도 선택하지 않을 때 dp에는 dp[i][0]으로 들어간다.1행을 선택하면 dp[i][1], 2행을 선택하면 dp[i][2]로 들어간다. 편의상 MAX(a, b)는 a와 b중 더 큰값을 반환하고, MAX3(a, b, c)는 a, b, c 중 제일 큰값을 반환한다.1) 아무것도 선택하지 않을 때 그 이전 열까지 합이 최대가 되는 dp의 값을 그대로 갖는다.ex)dp[3][0]=MAX3(dp[2][0], dp[2][1]. dp[2][2])가 된다..
-
2163번 : 초콜릿 자르기알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 5. 08:43
아주 쉬운 dp로 구성할 수 있다.입력받은 N과 M중 하나(N)를 고정시켜놓고 다른 하나를 1부터 M까지 증가시키면 된다.dp[1]은 Nx1의 초콜릿을 자르는 횟수인 N-1을,dp[2]는 Nx2의 초콜릿을 자르는 횟수인 dp[1]+N - 1 + 1(가로로 한번 추가)이렇게 증가시켜 나가면 된다. #include int N, M, dp[301];int main() {scanf("%d %d", &N, &M);dp[1] = N-1;for (int i = 2; i
-
1010번 : 다리 놓기알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 5. 01:04
처음에는 고3 확통때 배우는 조합 식인 을 이용하려 했으나 계산 과정에서 long long int 자료형도 담아낼 수 없는 값이 나와서 어쩔수 없이 조합 식을 dp에 적용하였습니다.dp[i]는 i개 중 N개를 고를 때의 경우의 수입니다. N이 3일때,dp[6]은 이고,dp[7]은 입니다. dp가 6에서 7로 변할때 4를 나누고 7을 곱한 것 처럼 dp가 i-1에서 i로 변할 때는 dp[i]=dp[i-1] * i / (i-N)가 됩니다.따라서 각 케이스마다 dp[M]까지 테이블을 채우면 쉽게 답이 나옵니다. 이 경우에는 값이 int 자료형에 충분히 들어갑니다. #include int dp[31];int main() {int T;scanf("%d", &T);while (T--) {int N, M;scanf(..
-
2156번 : 포도주 시식알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 4. 17:31
약간 복잡한 dp테이블을 세워야 하지만 2579번 계단 오르기와 많이 비슷하다.dp를 세울 때 i번째에 자신이 포함될 때와 포함되지 않을 때 두가지의 경우를 생각해 주면 된다. 왜냐하면 i+1, i+2에서 i번째를 포함 할지 안할지 모르기 때문이다.dp[i][j]는 i번째에 j가 0이면 i번째를 포함하지 않는 것, 1이면 i번째를 포함하는것을 의미한다.그렇다면 어떻게 해야할까? 우선 dp[1][0]과 dp[1][1]은 각각 0과 arr[1]로 초기화한다.i번째에 자신이 포함되지 않을 때는 dp[i-1][0]과 dp[i-1][1]을 비교(i-1번째 수를 포함시키는 경우와 포함시키지 않는 경우를 비교)해서 더 큰값을 이용한다.i번째에 자신을 포함할 때는 조금 복잡해진다. 연속해서 3번을 뽑을 수 없으니 이 ..
-
1932번 : 정수 삼각형알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 4. 14:38
dp로 해결했습니다. 레벨을 i라고 할 때 그 전레벨인 i-1레벨에서 각각의 정수 j (i-1레벨에 대한 j는 총 i-1개만큼 있습니다)에 대한 dp를 해당 칸을 포함한 정수의 합의 최댓값으로 설정합니다. 즉 dp[i][j]는 그 전 레벨의 인접한 두 노드중 더 큰 값을 선택합니다.여기서 arr[i][j]의 그 전레벨에 인접한 두 노드는 arr[i-1][j-1] 와 arr[i-1][j]입니다. ex)arr[3][2]의 그 전레벨에 인접한 두 노드는 arr[2][1]와 arr[2][2]가 됩니다.하지만 여기서 한가지 생각해보아야 할 것은 arr[2][2]의 전레벨에 인접한 두 노드는 arr[1][1]과 arr[1][2]가 되어야 하는데 arr[1][2]에는 값이 없습니다. 이것은 초기화를 모두 삼각형에 들..