728x90 반응형 Python169 2022.03.18 [백준] (python 파이썬) 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 이 문제는 0-1 배낭문제(0-1Knapsack Problem)이다. 왜냐하면 물건을 나누지 못하고 가진 물건으로 가방에 넣어 최대 가치를 만들어야 하기 때문이다. dp배열을 (n+1)(k+1)배열의 크기로 만든다. 이유는 조건에 따라 이전의 값과 비교해야 해서 n,k보다 1씩 큰 배열을 만들었다. 각 물건별 각 무게로 for.. 2022. 3. 18. 2022.03.17 [백준] (python 파이썬) 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 이 문제는 그래프를 이용해 각 번호에서 갈 수 있는 번호를 저장했다. 이 후, 각 번호에서의 케빈 베이컨의 수가 최저인지 확인 하기 위해 min과 최저이면 어떤 번호에서 최저인지 확인하기 위해 min_p를 선언했다. 그리고 for문을 돌려 각 번호에서의 케빈 베이컨 수를 bfs를 이용해서 구했다. 그리고 이전의 케빈 베이컨 수와 비교하여 작으면.. 2022. 3. 17. 2022.03.14 [백준] (python 파이썬) 거스름돈 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 풀이 다음 문제는 최소한의 동전의 갯수로 거스름돈을 줘야 하기 때문에 먼저 거스름돈 액수 n을 가장 큰 단위의 동전인 5로 나눈 몫을 cnt에 더해주고 n을 n%5(n을 5로 나눈 나머지)로 업데이트해준 뒤 3가지 조건을 정해주었다. n이 2로 나누어 떨어지지 않고 cnt가 0일 때 n이 2로 나누어 떨어질때 위의 두조건을 모두 만족하지 않은 조건이 있을때(cnt가 0이면서 n이 2로 나누어 떨어지지 않을때) 1번의 조건은 cnt가 0보다 크기 때문에 cnt에서 1을 빼고 n에 5를 더해주면 n은 짝수가 되면서 나누.. 2022. 3. 14. 2022.03.10 [백준] (python 파이썬) IOIOI https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 풀이 Pn은 'IO'가 n번 나오고 마지막에 'I'가 나온다. 여기서 규칙을 찾으면 중간의 I가 겹치면서 IOI가 n번 반복되는것을 확인할 수 있다. 각 인덱스에서 IOI의 패턴인지 확인하고 맞으면 check를 증가시킨다. 만약 check가 n과 같으면 cnt을 증가시키고 check를 1 감소시킨다. 이유는 이미 하나의 만족하는 .. 2022. 3. 10. 이전 1 ··· 8 9 10 11 12 13 14 ··· 43 다음 728x90 반응형
