본문 바로가기
728x90

전체 글423

[python] 백준 1744 수 묶기 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 해결 1보다 큰 양수는 더하는 것 보다 곱하는 것이 이득 1은 더하는 것이 이득 0은 아무런 영향이 없지만 음수가 있을때 음수를 곱해주면 0을 만들 수 있다. 음수는 음수끼리 곱하면 양수가 된다. 우선순위 큐를 통해 1보다 큰 양수, 음수를 따로 리스트를 분리해서 배열한 후 그 안에서 각각 절대값이 큰 것끼리 곱한다. 양수 리스트에 수가 남으면 더한다. 음수 리스트에 수가 남았고 0인 수가.. 2023. 2. 23.
[python] 백준 1715 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 해결 작은 수의 카드 묶음의 크기를 가진 것 부터 계산을 하는 것이 이득이라는 것을 알 수 있다. 리스트를 쓰고 sort를 쓰면 시간 초과가 난다. 우선순위 큐 (heapq 나 PriorityQueue를 쓰면 좋겠다는 생각으로 풀었다. CODE import sys import heapq n = int(input()) A = [] for _ in range(n): heapq.he.. 2023. 2. 23.
[python] 백준 2343 기타 레슨 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 해결 블루레이 크기란 무엇인가? => 컴퓨터 메모리로 생각하면 편하다. ex) 블루레이 크기 17이면 수의 합이 17이 될 때 까지만 메모리 저장 가능 메모리 크기는 강의 길이가 가장 큰거 이상이여야 한다. 메모리 크기는 모든 강의 길의 합 이하여야 한다. 따라서 메모리 크기의 최소지점과 최대지점 투 포인터를 집아 이분 탐색을 해서 블루레이 크기중 최소를 출력하도록 한다. CODE import sy.. 2023. 2. 23.
[python] 백준 2023 신기한 소수 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 풀이 두자리 이상일때(n≥2) 맨 앞자리는 소수만 가능(2,3,5,7) 나머지 자리는 홀수만 가능(1,3,5,7,9) 그래서 앞자리 만드는 것 부터 시작.(2, 3, 5, 7) 그 다음 수를 이어 붙일 때 소수인지 확인하고 소수이면 이어붙이고 아니면 다른 수 찾기 n자리 수가 되었을 때 출력 전형적인 DFS로 풀 수 있다. CODE import sys sys.setrecursion.. 2023. 2. 22.
728x90