알고리즘/백준(acmicpc.net) 문제풀이
-
1050번 : 물약알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 14:15
https://www.acmicpc.net/problem/1050 1050번: 물약 첫째 줄에 LOVE를 1만큼 만드는데 드는 비용의 최솟값을 출력한다. 만약 그 값이 1,000,000,000보다 크다면 1000000001을 출력한다. 만약 LOVE를 만드는 것이 불가능 하다면 -1을 출력한다. www.acmicpc.net N개의 주어진 재료와 M개의 조합식(또는 새로운 재료)를 갖고 LOVE를 만들 수 있는지 , 만들 수 있다면 그 최솟값은 무엇인지 구하는 문제이다. 아이디어 : 우선, 주어진 재료들의 이름과 비용은 map을 사용해서 나타낼 수 있다. 조합식들은 항상 a=k1*m1+k2*m2+... 꼴로 나타낼 수 있으며 파싱을 잘 해서 {계수, 재료이름} 꼴로 나타낼 수 있다. M제한이 50이고, 모..
-
1047번 : 울타리알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 11:20
boj.kr/1047 1047번: 울타리 첫째 줄에 N이 주어진다. N은 2보다 크거나 같고, 40보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 나무가 심어져 있는 위치와 그 나무로 만들 수 있는 울타리의 길이가 순서대로 주어 www.acmicpc.net 아이디어 : 기준을 나무가 아닌, 울타리, 즉 직사각형에 초점을 맞추자. 직사각형은 가로선 2개와 세로선 2개로 만들 수 있고, 가로선 2개의 안쪽 영역과 세로선 2개의 안쪽 영역의 겹치는 부분이 곧 직사각형의 내부 영역이 된다. 가로 기준으로 나무(=점) 2개, 세로 기준으로 점 2개를 골라서 이 4개의 점이 이루는 직사각형을 먼저 구한다. 그 다음 직사각형에 포함되는 점들과 포함되지 않는 점들로 나눈다. 포함되지 않는 점들은 다 잘라놓고..
-
1074번 : Z알고리즘/백준(acmicpc.net) 문제풀이 2018. 7. 11. 22:21
처음엔 재귀함수로 짜다가 시간초과가 나서 수학적으로 접근해 보았습니다. 쪼개는 방법은 단순합니다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 쪼개죠. 쪼개는 기준도 단순합니다. 처음 시작할 때 2^(N-1)의 길이로 자르고 자르는 것을 반복할 때마다 1/2씩 줄어듭니다. N=2일 때, (3, 1) 자리 숫자를 알고 싶다면 1) 범위(쪼개는 길이)가 2일 때 : x=3/2=1, y=1/2=0 이므로 왼쪽 아래자리, x와 y에 각각 2로 나눈 나머지를 저장하고 범위를 2로 나눕니다. 2) 범위가 1일 때 : x=1/1=1, y=1/1=1 이므로 오른쪽 아래자리. 이때 1)에선 범위의 제곱 * 2만큼 res에 더해줍니다.(0 + 2^2 * 2 = 8) 2)에선 범위의 제곱 * 3만큼 res에 더해..
-
11729번 : 하노이 탑 이동 순서알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 18. 10:14
이동 횟수는 dp로, 이동 순서는 재귀적으로 짜보았습니다.우선 이동 횟수부터.원판이 1개 있을 때의 이동 횟수는 1원판이 2개 있을 때의 이동 횟수는 3원판이 3개 있을 때의 이동 횟수는 7원판이 4개 있을 때의 이동 횟수는 15... 이것은 원판 N개가 1번에서 3번으로 이동할 때1) N-1개가 1번에서 2번으로 이동 / 이동 횟수 : dp[N-1]2) 가장 아래에 있던 원판이 1번에서 3번으로 이동 / 이동 횟수 : 13) 2번에 옮긴 모든 원판을 다시 2번에서 3번으로 이동 / 이동 횟수 : dp[N-1]이런 순서로 됩니다.이동 횟수를 모두 세어보면 결국 2*dp[n-1]+1번이 됩니다. (사실 dp를 안세워도 이동 횟수는 2의 n제곱-1번과 같습니다) 이제 이동 순서를 구해보겠습니다.원판을 이동시..
-
1436번 : 영화감독 숌알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 18. 09:10
이 문제는 666이 들어가면서 N번째로 작은 수를 찾는 문제입니다.즉 666, 1666, 2666, 3666, 4666, 5666, 6660, 6661, ... 이런식으로 된다는 것이죠.저는 666부터 조건을 만족할 때마다 N을 빼주면서 마침내 0이 되면 반복문을 탈출하도록 설정 했습니다. (브루트 포스) 수를 찾을 때마다 재귀를 돌려가면서 6이 연속되있는지 판단하기 보다는 아예 배열 안에 수를 한자리씩 넣어놓고 인덱스로 비교하는게 편할 것 같았습니다. 그래서 arr[10]을 설정하고 arr[0]은 1의자리 수, arr[0]은 10의자리 수 ,,, 이런식으로 세웠습니다. up()은 일의자리 수에 +1을 해주는 함수입니다. N이 0이 되었을 때는 가장 큰 자리수부터 차례대로 출력해야 합니다. 이때 처음부터..
-
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