220519_w5_랜덤유형 - Sunny-W-Park/elice-sw2-algorithms GitHub Wiki
박선우 - #9084 동전
문제 해석
- 주어진 동전으로 M원 만드는 경우의 수 구하기
접근
- dp = [0] * (M+1)
- 만들 수 있는 M원의 경우의 수 모두 dp에 저장
- coins: 주어진 동전 종류
- 이중 for문으로
풀이 과정
- dp[0] = 1로 설정
- dp[j] = dp[j - coin]으로 이전까지 누적된 경우의 수를 더해주기
for i in coins:
for j in range(1, M+1):
if j - i >= 0:
dp[j] += dp[j-i]
- coin을 하나만 더 보태면 만들 수 있기 때문에 이전 경우의 수와 동일함
- ex) 동전 2, 3이 주어질 경우 5 만들기
- dp[2] = dp[2-2] = 1
- dp[3] = dp[3-2] + dp[3-3] = 1
- dp[5] = dp[5-2] + dp[5-3] = 2
백성호 - #1251 단어나누기
문제 해석
- 주어진 단어를 세 개의 더 작은 단어로 나눈다. 단, 각 단어의 길이는 1 이상이다.
- 나눈 세 개의 단어 각각 앞 뒤를 뒤집고, 다시 원래의 순서대로 합친다.
- 이런 과정으로 만들어질 수 있는 새로운 단어들 중에 사전 순으로 가장 앞에 있는 단어를 출력해야 한다.
접근
- 이중 for문을 활용하여서 단어를 1 이상의 길이로 삼등분한다.
- Python의 index 문법을 활용하여, 각 단어를 뒤집는다.
- 나눈 단어를 다시 합친 후, 정답 배열에 추가한다.
- 정답 배열을 알파벳 순으로 정렬한 후, 첫 번째 원소를 출력한다.
풀이 과정
- 문자열을 입력 받고, 문자열의 길이를 n으로 저장한다.
- 이중 for문을 활용하여 문자열을 i, j, n-i-j 길이로 나눈다.
- 나눈 문자열을 string[::-1] 문법을 활용하여 뒤집고, 하나의 문자열로 합친다.
- 합친 문자열을 ans_list 배열에 append하고, sort 함수로 정렬한다.
- 배열의 첫 번째 원소를 출력한다.
지의신 - #2293 동전1
문제 해석
- n,k : n가지의 종류의 동전, 그 가치의 합이 K원이 되어야 함
- n개의 줄에 각 동전의 가치가 주어짐
- 각 동전의 합이 K가 되는 경우의 수를 구하라, 사용한 동전의 구성은 같은데 순서만 다른 것은 같은 경우로 침
접근
- dp 활용 각 idx의 dp값은 해당 금액에서의 경우의 수
- 각 동전의 종류를 순회, ex. 1, 2, 5
- dp를 순회
- 특정 가치를 가진 동전을 썼을 때 합이 dp의 인덱스 값이 되는 경우의 수가 있다면 dp에 기록하기
풀이 과정
- coins 배열 내에 각 코인의 종류를 대입
- dp배열 초기화, 인덱스 0은 동전을 1개만 쓸때의 경우의 수를 고려하기 위해 선언
- for문: 각 코인의 종류를 순회, coin 각 코인의 가치의 값
- dp를 순회하는데 만약에 coin의 값이 5원 짜리라면 dp[1]~dp[4]는 고려할 필요가 없다, 그러므로 dp[5]부터 순회, range(coin, k+1)
- dp[인덱스]에 dp[인덱스-coin가치]를 더하면 된다.
- dp[k]를 출력
김재민 - #11279 최대힙
문제 해석
- N : 이후에 들어올 연산 개수
- x : 연산. N번 입력받는다.
- 만약 x가 자연수라면 배열에 넣고 0이라면 지금까지 입력받은 값 중 가장 큰값을 출력 후 제거
접근
- heapq 활용
- heappush할 때 tuple을 이용하여 (-x,x)롤 push 한다면 tuple[1]이 내림차순으로 가장 큰 값이 가장 앞에 오게 된다.
풀이 과정
- hq 리스트를 heap화(heapify) 한다.
- 연산 x들을 N만큼 입력받아 input_list에 저장
- input_list for문 순회
- 만약 x가 0일 경우 hq에 값이 있다면 hq을 pop하여 튜플의 1번 인덱스를 출력한다. 값이 없다면 0을 출력한다.
- 만약 연산 x가 자연수일 경우 (-x,x)롤 push