이지코딩

예제를 보면 알겠지만, 문자열이 꽤나 길어서.... 편하게 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] 이..

dp 문제에서 찾기 힘든 낮은 랭크의 문제. 초콜릿 자르기다. n*m인 초콜릿을 1*1 로 모두 자르는데 몇번을 쪼개야 하는지를 묻고 있다. 최소한으로 쪼개는 것이지만, 한번에 길게 자르는것을 생각하면 n*m 과 m*n 은 항상 같은 횟수를 가지게 된다. dp문제를 풀때 첫번째로 해야하는것. 초기값 설정이다. 이 문제에서 초기값은 1*m 또는 m*1 크기의 초콜릿을 자르는 횟수가 될것 이고, 이는 m-1회 일것이다. 이후 해야 하는것. 점화식 세우기. 3*3을 생각해보면 아래 그림처럼 나눌수 있을 것이다. 이렇게 잘라보면, 3*1 조각과 3*2 를 각각 최소한으로 자르는 횟수 +1 이 될것이다. dp[n][m]이 n*m을 최소한으로 자르는 횟수라고 가정하면, dp[n][m] = 1+dp[n][1] +dp..