이지코딩

https://www.acmicpc.net/problem/15953 15953번: 상금 헌터 첫 번째 줄에 제이지가 상상력을 발휘하여 가정한 횟수 T(1 ≤ T ≤ 1,000)가 주어진다. 다음 T개 줄에는 한 줄에 하나씩 제이지가 해본 가정에 대한 정보가 주어진다. 각 줄에는 두 개의 음이 아닌 정수 a(0 ≤ a ≤ 100)와 b(0 ≤ b ≤ 64)가 공백 하나를 사이로 두고 주어진다. www.acmicpc.net 문제가 길어서 문제 이미지는 생략하고..... 카카오 2018 코드페스티벌 예선 1번 문제다. 이 문제처럼 '등수'에 따라 값이 달라지는 문제는 개인적으로 array에 미리 집어넣어 배열에 접근하는 방시깅 제일 빠른것 같다. 또한, 함수에 들어오는 파라미터가 들어오자마자 간단한 조건식을 ..

예제를 보면 알겠지만, 문자열이 꽤나 길어서.... 편하게 python을 사용하였다. 솔직히 말해서 두번 틀렸다...ㅎㅎ... 옷의 조합이 꼭 2개의 조합일 것이라고만 생각해서 경우의 수를 짜다보니 3개 이상의 조합을 빼먹을 것이다. 일단, 문자열 입력에서 띄어쓰기를 기준으로 뒤에 있는 옷의 종류만 알면 되기에 split()을 통해 뒷 단어만 따로 때서 dict 형에 집어 넣었다. Dict형을 사용한 이유는 옷의 종류가 같은지 다른지를 판단할때 A in ex_dic를 사용하면 매우 편해서 ㅎㅎㅎ 이후 딕셔너리의 밸류값만 따로 리스트로 만들어 연산을 수월케 했다. 이제 알고리즘을 알아보자. 옷의 종류 a,b,c가 각각 2,3,4개 있다고 가정하고, 각 원소의 갯수에 따른 조합의 경우의 수를 따져보자. 1개..

시간 제한을 생각하지 않고 풀어서 몇번 틀렸다...ㅎㅎ 다들 시간 제한 잘 보고 어떻게 풀지 생각 합시다! 일반적으로 while문을 사용하게 된다면 10억번을 돌 수도 있게 되어 10초라는 어마 무시한 시간이 걸리게 된다. 그래서 수식을 만들어 생각 해야 한다. D-1 째날, 달팽이가 (V-A)m 까지 올라가있다면, D쨋날 탈출을 할 수 있다는 점을 생각하여 식을 꾸리면 다음과 같다. (A-B)(D-1) >= (V-A) 위 식을 통해 D를 구하려는 식으로 바꾼다면, D >= (V-A) / (A-B) + 1 일 것이고, D가 만약 3.33처럼 소수점을 가진다면, 4일이 걸린다는 것을 알 수 있다. 위처럼 실수인지 정수인지 확인하는 if문을 통해 출력을 하면 된다. 실수인지 정수인지 확인하는 방법: t가 실..

문제에서 언급한 계단수를 보면, 앞자리 숫자에 뒷자리 숫자가 영향을 받는다. 여기서부터 느껴지는 dp의 향연...... 차근차근 접근해 보자. 계단수의 길이가 1일때는 1부터 9까지 각 1개씩의 계단수를 가진다. 후에 편의를 위하여 0 또한 1개의 계단수를 가진다고 하자. 계단수의 길이가 2개 일때를 살펴보자. 계단수의 시작이 0이 될 수 없으므로 1부터 살펴보면, 1뒤에는 0과 2가 올것이다. 즉, 계단수의 길이가 1개 적을때의 값을 사용하게 된다. 2뒤에는 1,3이 올것이므로 동일하다. 다만, 시작하는 수가 9일 때는 뒤에 8만이 올 수 있다. 또한, 계산의 편의를 위해 0을 계산해 보면, 0으로 시작할 경우, 뒤에는 1만 올 수 있다. 이것을 표로 정리해보자. 다음과 같이 각 길이별/ 시작 숫자별로..

입력받은 정렬된 array 에서 원소갯수가 6개인 독립집합을 모두 구하는 문제이다. 흠.... 문제에 '모든' 이라는 단어를 보고 처음든 생각은 브루트포스 또는 DFS(깊이우선탐색) 인데, 정렬되어있는 배열에서 순차적으로 6개를 선택하면 되므로 DFS알고리즘과 좀더 가까운듯 하다. 입력받은 배열이 [1,2,3,4,5,6,7]일때, 6개를 순차적으로 선택하는 방법으로 아래의 그림처럼 탐색하는 것이 먼저 떠올랐다. 음...... 느낌상 윗 레벨의 숫자가 결정되면, 가능한 원소의 갯수만큼 아래 레벨에서 선택하면 될듯 하다. 즉, 첫 숫자로 1을 선택하게 되면, 뒤에 더 올수 있는 원소의 갯수는 5개 일것이고, 2와 3이 올수 있을 것이다. 1 뒤에 올 숫자로 2를 선택하면, 뒤에 올 수 있는 원소의 갯수는 4..

N개의 정수 원소가 있는 수열에서 부분수열의 합이 S와 같은 경우의 수를 찾는 문제이다. 연속적인 수열이 아니므로, 모든 부분수열을 찾는 과정이 필요하다. 모든 것을 다 해보는 방법을 Brute-Force(완전탐색)이라고 한다. 일단, [1,2,3] 라는 수열이 있을경우, 부분집합은 [1], [2], [3], [1,2], [1,3] [2,3] [1,2,3] 처럼 나올 것 이다. [1,3]처럼 연속되지 않는 수열을 뽑아내려면 이중반복문 만으로는 충분치 않아보이는데... 흠..... 아래 그림으로 좀더 방법을 찾아보자. 위 그림처럼 진행이 가능하다면, 3개의 원소가 있는 array 에서는 모든 부분수열을 찾을수 있다. 항상 저 나무를 그리면 DFS/BFS 가 먼저 생각나긴 하는데....흠.... 아무튼, 위..

문제를 읽어보면 알겠지만, 무조건 큰 수를 작게 만드는 것의 반복이 아니다. 예를 들면 10을 (/2, -1, /2, /2)를 하면, 각 순서마다 가장 작은 값을 뽑아왔지만, (-1, /3, /3) 처럼, 나누는게 우선순위가 아니였다. 즉, /3,/2,-1 순서가 우선순위를 가지지 않는다. 그래서 1부터 4까지의 수를 하나씩 해보았다. n = 1, 0번 n = 2, 1번 n = 3, 1번 n = 4, 1) -1 을 할 경우, n = 3 이 되므로 2번. 2) /2 를 할 경우, n = 2 가 되므로 2번. 3) /3 은 불가능. 즉, dp[n] 은 (n-1)를 1로 만드는 최소횟수 +1 또는 (n/2)를 1로 만드는 최소횟수 +1 또는 (n/3)을 1로 만드는 최소횟수 +1 이 될 것이다. 이런식으로 d..

먼저, 입력받은 값은 dp[0][n]에, 계산한 합은 dp[1][n]에 넣는다고 한다. 조건에 의해 마지막 계단은 꼭 밟아야 하므로, 상황을 2가지로 함축해 볼 수 있다. 1) 마지막 계단 과 그 전 계단을 밟을 경우 2) 마지막 계단과 그 전전 계단을 밟을 경우. 마지막 계단을 dp[0][n] 이라고 했을때, 연속된 3개의 계단을 밟을 수 없으므로, 1번의 상황에서는 dp[0][n-3]과 dp[0][n-1]을 밟았을 것이다. 즉, dp[1][n] = dp[0][n] + dp[0][n-1] + dp[1][n-3] 2번의 상황에서는 dp[n-2] 만 밟고 올라왔을 것이다. 이때에는 dp[1][n-2] 까지는 n-2 일때 계산이 되어있을 것이므로 dp[1][n] = dp[0][n] + dp[1][n-2] 이..