분류 전체보기27 BOJ백준 1890 점프 풀이(Python) 문제는 위와 같으며 전형적인 DP(Dynamic Programming)문제이다.DP의 의의는 이전에 계산했던 값들을 이번에 구할 값을 계산할 때 응용함에 있으므로 이를 중심으로 생각해보자. 예를 들어 A와 B라는 칸에서 C로 갈 수 있다고 해보자. 그렇다면 칸C까지 갈 수 있는 경우의 수는 칸A와 칸B까지 갈 수 있는 경우의 수의 합이 될 것이다.이를 이용하며 시작점부터 차례대로 게임판을 순회하며 각 칸에서 갈 수 있는 칸에 현재 칸까지 오는 경우의 수를 더해준다. 아래는 소스코드이다.123456789101112131415161718192021222324252627282930import sysN = int(sys.stdin.readline())board = []for i in range(N): temp .. 2019. 2. 6. BOJ백준 1748 수 이어 쓰기1 풀이(C++) 문제는 위와 같이 간단하다.단순히 연속된 수를 옆으로 쭉 나열하면서 N까지 이어썼을 때의 자릿수, 즉 문자열의 길이를 구하면 된다. 간단히 증가하는 자릿수의 규칙을 찾아보자 - 한 자리 수(1 ~ 9)123456789 -> 9자리- 두 자리 수(10 ~ 99)101112...979899 -> 180자리... 보다시피 (각 자리의 길이) * (각 자리 숫자의 개수) 가 해당 자리수까지 전부 더했을 때 증가되는 문자열의 길이임을 알 수 있다.만약 입력으로 받은 N이 네 자리 숫자라면 3자리 숫자까지는 전부 더해지므로 위의 공식대로 증가시키고 입력받은 숫자의 길이인4자리수 부터는 따로 계산해주면 쉽게 답을 구할 수 있을 것이다. 아래는 코드이다.12345678910111213141516171819202122#.. 2019. 2. 6. BOJ백준 1339 단어수학 풀이(Python) 문제는 위와 같다. 어렸을 때 많이 봤던 방식의 문제였지만 알고리즘 공부를 시작한지 얼마 안되었던 나에게는 어떻게 구현할지 약간 막막했었다.고민하다가 내가 접근한 방법은 먼저 각각의 알파벳에 곱해지게 될 숫자를 구한 후 곱해지게 되는 숫자가 큰 순으로 정렬한 뒤차례대로 알파벳 값과 곱해지게 될 숫자를 곱하며 더해주는 방식이였다. 예를 들어, GCF와 ACDEB가 있다면1. GCF = 100*G + 10*C + 1*F2. ACDEB = 10000*A + 1000*C + 100*D + 10*E + 1*B이므로 각 알파벳 별로 곱해지게 될 숫자는A : 10000B : 1C : 1010D : 100E : 10F : 1이다. 이를 Dictionary 를 이용하여 구현하였고 후에 정렬한 뒤 더해주니 답이 나왔다. .. 2019. 2. 6. 이전 1 2 3 4 5 다음
