sunrin
-
1107번 : 리모컨알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 17. 21:24
많은 좋은 방법들이 있겠지만 저는 모두 탐색하는 브루트-포스 방식을 택했습니다.구현하는 방법은 쉽지만 시간과 메모리가 많이 소모되는 방식입니다. 총 3가지 단계로 답을 찾을 수 있습니다.1. 각 자리의 숫자는 무엇이고 총 몇자리 수인지 파악하기2. 재귀적으로 값을 찾고(현재의 값과 맞춰야 할 값의 차이를 보면서) 가장 작은 값을 조사하기3. 값을 비교하기 총 몇자리 수인지 파악합니다.각 자리의 숫자를 num[6] 배열에 넣어줍니다.코드에선 sep() 함수와 sepa() 함수가 이를 처리합니다. find()함수는 두가지의 인자를 받습니다 : 현재의 값인 n, 그리고 그 n의 자리수를 알려주는 cnt.현재의 값과 처음에 입력받은 N의 값을 비교해주면서 (둘의 차이) + (n의 자리수인 cnt)의 최솟값을 구..
-
2941번 : 크로아티아 알파벳 : 숏코딩버젼알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 14. 16:10
조건 하나하나 설정하기 너무 귀찮아서 숏코딩을 목표로 짰습니다.두가지 방법을 생각해 봤습니다.1. 배열에 미리 문자열을 넣어놓는 방법2. define을 이용하는 방법 1번째 방법은 너무 정석적이라 2번째 방법을 택했습니다. MAX(a,b) 이런게 필요할 때 저는 주로#define MAX(a,b) (a)>(b)?(a):(b) 이렇게 쓰고 시작합니다. 여기에서 영감을 얻어서 많이 반복되는 "arr[i]==문자 && arr[i+1]==문자" 이런 것들을 줄이고자 했습니다.결국 완성된 것은 #define c(c,d) a[i]==(c)&&a[i+1]==(d)이것입니다.c(c,d)는 매크로이며 함수처럼 쓸 수 있습니다.a[i]는 배열을 의미하고 (c)와 (d)는 대입된 인자를 쓸 수 있습니다. 결국 맞은 사람 순위..
-
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(..