끄적끄적

문제풀이

1. 딕셔너리 자료구조를 활용하여 생성자의 개수를 세어줍니다. 딕셔너리 dic의 key는 생성자가 되고, value는 생성자의 개수가 됩니다.

2. 1부터 10000까지의 숫자 n의 d(n)을 구하여, 위의 딕셔너리에서 key d(n)의 value에 1을 더해줍니다.

3. 1부터 10000까지의 숫자들을 key로 하여, value가 0인 값을 출력합니다.

Python Code

문제링크

문제풀이

1. 각 요소가 (서류 순위, 면접 순위)인 리스트 l을 만든 후, 서류 순위를 기준으로 l을 정렬해줍니다.

2. 정렬된 l에서 앞에서부터 튜플을 하나씩 꺼내며 면접 순위가 이전에 선발된 사람보다 높은(숫자가 낮은) 사람을 선발하게 됩니다.

백준의 두번째 예시

[(1, 4), (2, 5), (3, 6), (4, 2), (5, 7), (6, 1), (7, 3)]

를 살펴보면 다음과 같습니다.

- 먼저 서류 1등은 당연히 뽑히게 됩니다. 2, 3등은 서류 순위, 면접 순위 모두 서류 1등보다 낮으므로 선발되지 않습니다.

- 서류 4등의 경우, 서류 1등보다 면접 등수가 높으므로 선발됩니다.

- 서류 5등의 경우에는 서류 4등보다 면접 등수도 낮으므로 선발되지 않습니다.

- 서류 6등의 경우에는 서류 4등보다 면접 등수가 높으므로 선발됩니다.

- 서류 7등의 경우에는 면접 등수도 서류 6등보다 낮으므로 선발되지 않습니다.

Python Code

Line 7 : l은 (서류 등수, 면접 등수)가 들어갈 리스트입니다. Line 7~10을 Line 6 한줄로 축약할 수 있습니다.

*축약할 경우 소요시간이 3584 -> 3996 ms로 길어지게됩니다.

문제 링크

문제풀이

1. 각 줄의 첫 번째 요소는 학생수, 그 다음 요소들은 학생들의 점수들이므로 평균을 구한 후, 평균 이상인 학생수를 구해 전체 학생수로 나눠준다.

2. *100을 한 후, 소수점 세자리로 끊어준다. '.3f' 포맷을 활용한다.

Python Code

문제 링크

문제풀이

1. 배열 자료구조인 dp에 n번째 음식의 만족도를 담습니다. 즉, dp[i]는 i번째 음식의 만족도입니다.

2. 배열 자료구조인 dp2에는 n번째 음식을 먹었을 때의 만족도의 최댓값을 담습니다. 즉, dp2[i]는 i번째 음식을 먹었을 때의 만족도의 최댓값입니다.

3. dp2의 요소는 다음과 같은 과정을 통해 얻습니다.

3-1. n번째 음식의 인덱스를 n, 만족도를 nth라 할때, dp의 n번째 이전의 요소들 중 nth보다 작은 값들에 해당하는 dp2의 요소를 모읍니다.

3-2a. 위 과정에서 모은 요소들 중 최댓값+nth가 dp2[n]이 됩니다.

3-2b. 위 과정에서 모인 요소가 없다면, n번째 이전에 먹을 것이 없다는 의미이므로 dp2[n]은 nth가 됩니다.

** dp의 이름을 별 생각없이 dp로 지었는데, dp2가 실질적으로 메모리제이션이 이루어지는 배열이고, dp는 동적프로그래밍과 큰 관련이 없습니다.

Python Code

문제 링크

문제풀이

1. dp의 각 요소의 의미는 다음과 같다.

dp[0] : 입력 받은 칸을 red로 칠했을 때 코스트의 최솟값
dp[1] : 입력 받은 칸을 green로 칠했을 때 코스트의 최솟값
dp[2] : 입력 받은 칸을 blue로 칠했을 때 코스트의 최솟값

2. 현재 칸의 페인트의 코스트 r,g,b를 입력받았다면, 위의 관계를 아래와 같이 쓸 수 있다.

dp[0] = min(dp[1],dp[2])+r
dp[1] = min(dp[0],dp[2])+g
dp[2] = min(dp[0],dp[1])+b

Python Code

문제 링크

문제풀이

세 개의 요소를 활용한 dp로 문제를 풀겠습니다.

1. 배열 자료구조인 dp의 각 요소의 의미는 아래와 같습니다.

dp[n][0] : n번째 행의 왼쪽 칸에 사자가 있을 경우의 수.

dp[n][1] : n행의 오른쪽 칸에 사자가 있을 경우의 수.

dp[n][2] : n행에 사자가 없는 경우의 수.

2. 각 요소의 점화식은 다음과 같습니다.

2-1. dp[n][0] = dp[n-1][1]+dp[n-1][2] ; n행의 왼쪽에 사자를 넣기 위해서는 윗행의 오른쪽에 사자가 있거나(dp[n-1][1]) 윗행에 사자가 아예 없어야(dp[n-1][2]) 합니다.

2-2. dp[n][1] = dp[n-1][0]+dp[n-1][2] ; n행의 오른쪽에 사자를 넣기 위해서는 윗행의 왼쪽에 사자가 있거나 윗행에 사자가 아예 없어야 합니다.

2-3. dp[n][2] = dp[n-1][0]+dp[n-1][1]+dp[n-1][2] ; n행에 사자를 넣기 않으려면, 윗행에 사자가 어디에 있든 아예 없든 상관 없습니다.

3. dp의 요소가 너무 커지지 않도록 %9901을 해주며, n=1부터 입력받는 N까지 진행해준 후, sum(dp[n])%9901을 반환합니다.

Python Code

문제링크

문제풀이

1. n,k,l을 입력 받습니다.

2. n번 3개의 정수로 구성된 리스트를 입력 받습니다.

3. 입력받은 리스트의 최솟값과 합계를 각각 k와 l과 비교합니다.

4. 입력받은 리스트의 최솟값과 합계가 각각 k와 l보다 크다면 answer에 1을 더하고, vip 리스트에 3명의 기록을 넣습니다.

5. answer를 출력하고, vip에 들어있는 기록들을 출력합니다. 저는 vip 리스트를 스트링으로 변환 후, 맨 앞과 맨 뒤의 대괄호를 지우고, re의 sub함수를 활용하여 ','를 지워 출력하였습니다.

Python Code

문제 링크

문제풀이

1. $k_t$를 길이가 t이고 k로 끝나는 오르막 수라고 하고 점화식을 세우면 다음과 같습니다.

$k_t = \sum_{l=0}^k l_{t-1}$

즉, 길이가 2인 1로 끝나는 오르막 수의 개수는 길이가 1인 0으로 끝나는 오르막 수의 합(한개(0))과 길이가 1인 1로 끝나는 오르막 수의 합(한개(1))인 2개입니다. 0 뒤에 1을 붙이고, 1 뒤에 1을 붙여 {00, 01} 두 개가 됩니다.

2. 위의 $k$를 1부터 $n$까지 올리며 계산한 후, $\sum_{k=0}^9 k_n$을 반환합니다.

Python Code

Line 4, 6 : 문제의 조건에 따라 %10007을 해줍니다.

문제링크