![]()
[문제] https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net [풀이] 처음에는 간단하게 sort 함수를 이용해 풀었는데 이는 O(nlogn)으로 우선순위 큐를 이용하면 O(logn)으로 시간복잡도를 줄일 수 있다. 우선순위 큐 사용시, 값을 바꿀 카드 2개를 우선순위 큐에 삽입만 하면 되기 때문에 매번 정렬해야하는 sort 보다 훨씬 효율적인 것이다. 따라서 cards 리스트를 만든 후 heapq 내장 모듈 사..
![]()
[문제] https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net [풀이] 우선 피보나치 리스트를 만들어 올바른 값을 미리 넣어준다. 문제에 n의 최댓값이 1,000,000,000이라고 했기 때문에 44번 째 피보나치 수열까지만 구하면 된다. 만들 수 있는 숫자 중 최소 개수로 n을 만들기 위해서는 n 이하의 수 중 가장 n과 가까운 수를 써야 한다. 문제에 나온 예시처럼 100을 만들기 위해서는 (3 + 8 + 89) 도 가능하지만 (3 + 8 + 34 ..
![]()
[문제] https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net [풀이] 우선.. for문을 두 번 쓰면 런타임 에러가 난다. 당연함. 100,000명을 2차 반복문으로 돌리면.. 따라서 반복문 한번에 비교를 끝내야한다. 그러기 위해 우선 첫 번째 점수를 기준으로 정렬을 한 후에 rank_asc 변수에 담는다. rank_asc 변수의 첫 번째 원소는 서류 심사가 가장 높은 사람이 오기 때문에 이 사람의 면접 결과가 몇 점이든 무조..
![]()
[문제] https://www.acmicpc.net/problem/1817 1817번: 짐 챙기는 숌 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책 www.acmicpc.net [풀이] 이 문제의 핵심은 책을 차례대로 박스에 넣을 수 있다는 것이다. 때문에 차례대로 반복문을 돌며 박스에 책을 넣었을 때 박스에 들어간 무게가 M을 넘는다면 박스 무게를 초기화 하여 현재 책의 무게를 담고 cnt를 1 증가시킨다. [코드] import sys N, M = map(int, sys.stdin.readline().split()) if N > 0: bo..
![]()
[문제] https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net [풀이] 입력받은 문자열을 한 글자씩 리스트에 넣는다. 첫 번째 문자가 0이면 zero_count를 1 더해주고, 1이면 one_count를 1 더해준다. zero_count: 0을 1로 바꿔야 하는 횟수 one_count: 1을 0으로 바꿔야 하는 횟수 반복문으로 문자열의 (i - 1) 인덱스와 (i) 인덱스의 값이 일치하는지 확인한다. 일치하지 않을 경우 (i) 인덱스의 값이 0이면 ..
![]()
[문제] https://www.acmicpc.net/problem/3578 3578번: Holes You may have seen a mechanic typewriter — such devices were widespread just 15 years ago, before computers replaced them. It is a very simple thing. You strike a key on the typewriter keyboard, the corresponding type bar rises, and the metallic letter mo www.acmicpc.net [풀이] 문제에 쓸데없는 설명들이 많은데 요약하자면 0, 4, 6, 9 를 타이핑 할 경우 종이에 구멍이 1개 생기고 8 을 타이..
![]()
[문제] https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net [풀이] 그리디 문제! 최종 결과는 신경쓰지 않고 일단 현재 가장 이익이 될 것을 선택한다. 여기서 현재 가장 이익이 될 것 = 거스름돈이 제일 작을 것 시간이 긴 버튼을 누르는 게 이익이 되기 때문에 5분부터 차례대로 답을 찾아간다. [코드] import sys T = int(sys.stdin.readline()) A, B, C = 300, 60, 10 if T % C != 0..
![]()
[문제] https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net [풀이] 지역의 높이 정보를 set 으로 모아 어떤 높이의 건물이 있는지 비가 얼마나 오는 지 모르기 때문에 0부터 건물 최고 높이까지 비를 내리게 한다. 건물의 높이는 지역의 높이 정보를 set 으로 모아 확인한다. 건물 높이보가 현재 내리는 비 높이보다 크고 아직 그 건물을 방문한 적이 없으면 count 를 하나 올리고 bfs 함수로 들어간다. 현재 기준이 되는 건물의 상하좌우 에 있는 건물..
![]()
[문제] https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net [풀이] 2022.08.25 - [문제풀이/BOJ] - [Python] BOJ/백준 2458번 키 순서 [Python] BOJ/백준 2458번 키 순서 [문제] https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명..
