본문 바로가기

PS

(18)
[BOJ] 2217번 로프 문제 - Python www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 로프를 역정렬해서 계산한다. 예를 들어서, 로프가 [10, 8, 6, 4, 2] 이렇게 있다고 치면, 앞에서부터 하나씩 추가하면서 계산해보면 들 수 있는 최대무게는 [10, 16, 18, 24, 10]이 된다. 로프의 개수 x 하중의 최소가 되는 것이다. from sys import stdin input = stdin.readline N = int(input()) rope = [] for _ in ra..
[BOJ] 1309번 동물원 문제 - Python www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 생각보다 어려웠다.. k번째 행에 대한 경우는 다음과 같다. 1. k번째 행에 사자가 없는 경우 이는 사실 k-1번째 경우의 수와 같다. k번째 행만 빼고 전부 다 배치하는 건 k-1번까지만 배치하는 것과 같다. 2. k번째 행의 왼쪽에 사자가 있는 경우 이는 k-1번째 경우에서 k-1번째 행의 왼쪽에만 사자가 없는 경우와 같다. 당장 내 바로 위에만 사자가 없으면 얼마든지 배치할 수 있기 때문이다. 3. k번째 행의 오른쪽에 사자가 있는 경우 2의 경우와 같다. 그럼 다음과 같이 풀이하면 된다. 두 개의 배열은 선언한다. 각각 dp1과 dp2..
[BOJ] 15666번 N과 M (12) 문제 - Python www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복은 가능하나 비오름차순으로 출력해야한다. 따라서 입력받은 숫자를 set 으로 변환 후 다시 list 로 변환해서 겹치는 것을 제거해주고 sort 한뒤 뽑기만 하면 된다. element 안에 아무것도 없을 때는 그냥 순서대로 집어넣고 원소가 있을 때만 비오름차순으로 뽑아준다. N, M = map(int, input().split()) numbers = list(map(int, input().split())..
[BOJ] 15664번 N과 M (10) 문제 www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 꽤나 곤란했던 문제다. 2번 예시 처럼 9 7 9 1이 주어졌을 때, 9가 두개라서 9 9가 나타나지만 1 9 는 한번만 나타나야 한다. 따라서 overlap 이라는 변수를 통해서 해당 depth 에서 그 수를 사용했는지 안했는지를 구분했다. 어차피 정렬이 되어있기 때문에, 같은 수가 중복 사용되는 경우는 다 걸러 낼 수 있다. N, M = map(int, input().split()) numbers = l..
[BOJ] 15665번 N과 M (11) 문제 www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 같은 수가 여러번 주어져도 무시하고 중복순열로 뽑으면 된다. 따라서 set 을 이용해서 중복을 제거하고 다시 list 로 바꿔서 그냥 중복순열을 뽑아냈다. N, M = map(int, input().split()) numbers = list(map(int, input().split())) numbers = list(set(numbers)) numbers.sort() element = [] def dfs(de..
[BOJ] 2153번 소수 단어 문제 1D1P Day76 BOJ 2153번 소수 단어 문제 - 2021.01.19 - 2153.py 출처 : (BOJ_2153번_소수 단어)[https://www.acmicpc.net/problem/2153] 1도 소수라는 조건을 기억하자. 미리 소수 배열을 만든다. 각 알파벳은 ord를 이용해서 정수로 변환하자. 에라토스테네스의 체를 이용하는 게 더 효율적이겠지만, 그냥 2000개의 배열을 각각 소수 검사했다. 나타날 수 있는 소수의 최대값이 52 * 20 정도이기 때문에 2000 정도면 충분할 것이다. # 1D1P Day76 BOJ 2153번 소수 단어 문제 - 2021.01.19 word = input() primes = [1] * 2000 primes[0] = 0 primes[1] = 1 for i i..
BOJ - 2133번 타일 채우기 www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 3x홀수 인 경우에는 만들 수가 없으므로 다 0이다. DP[2] = 3이고 DP[4] = 11이다. 2개짜리 2개를 붙여서 만들 수 있으므로 3x3인데 특이케이스가 2개가 더 생겨서 11이 된것이다. DP[6]도 그려보면 4개짜리에 2개짜리를 붙인 11x3개를 제외하고 특이케이스가 2개가 더 생긴다. 근데 우리가 놓친 특이케이스가 또 있다. 11x3은 4개짜리 오른쪽(혹은 왼쪽)에 2개짜리를 붙이는 경우를 뜻하는데 대부분의 경우는 좌우대칭이 고려되나 4개짜리를 계산할 때 나타난 특이케이스에 대해서는 고려가 안된다. 그 특..
BOJ - 1699번 제곱수의 합 http://acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 며칠동안 못 푼 문제다. 최소 몇개의 제곱수로 표현 가능한가? 를 찾는 문제다. 일단 DP[i] = i로 초기화 한다. 왜냐 1을 i개 더하는게 최댓값이니까 그리고 제곱수를 작은것부터 가져와서 생각한다. 제곱수를 k, 해당 수를 N이라고 한다면 DP[N] 이랑 DP[N-k]+1 중에 작은 것으로 DP[N]에 다시 값을 넣어주면 된다. 코드는 다음과 같다. /* acm..