728x90 조합론5 [python] 백준 1328 고층 빌딩 https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 문제 해결 dp를 써야겠다라는 생각이 드는데 어떻게 써야할지 고민이 되는 문제 n이 1이상 100이하이기 때문에 삼 중 반복문을 써도 괜찮다. dp[i][j][k]를 i개의 빌딩이 있을 때 왼쪽에서 보면 j개 오른쪽에서는 k개 보이는 배열가지수라고 하자. 그러면 dp[1][1][1] =1 이 된다. 가장 기본 값 i-1개의 빌딩이 배열되어있다고 하자. 이제 빌딩 하나를 더 세워 dp[i][j][k.. 2023. 5. 8. [python] 백준 17471 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 해결 삼성 A형 기출문제 딱 봐도 완전탐색 문제이다.(2 ≤ N ≤ 10, 1 ≤ 구역의 인구 수 ≤ 100) 문제는 combination을 사용하여 모든 경우의 수를 다 고민을 해야하나인데... 맞다. 1개부터 n//2 개까지 선거구를 뽑은 다음 다 연결 되었는지 확인하고 나머지 선거구끼리도 모두 연결되었는지 확인해야한다. 모두 연결이 되면 두 집단의 인구 차이를 이전과 비교해서 작은 값을 저장한다. 삼성은 i.. 2023. 4. 26. [python] 백준 6603 로또 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 문제 해결 combination(조합) 라이브러리만 쓸 줄 알 면 쉬운 문제 for문 반복으로 출력하면 된다. CODE from itertools import combinations import sys input = sys.stdin.readline while 1: S = list(map(int, input().split())) if S[0] == 0:break for comb in c.. 2023. 1. 12. [python] 백준 10973 이전 순열 https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문제 해결 10972와 반대 문제 https://thought-process-ing.tistory.com/92 [python] 백준 10972 다음 순열 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문 thought-process-ing.tistor.. 2023. 1. 8. 이전 1 2 다음 728x90
