본문 바로가기

codingtest287

[python] 직사각형 만들기 문제 N개의 막대기 중 일부를 잘 배치해서 직사각형을 만들고자 한다. 직사각형을 만들기 위해서는 길이가 같은 막대기 두 쌍이 필요하다. 같은 쌍에 속한 막대기들을 마주 보게 배치하고, 다른 쌍에 속한 막대기들을 수직으로 배치하면 직사각형을 만들 수 있다. 길이가 a인 막대기와 길이가 b인 막대기 쌍을 사용해서 직사각형을 만들었을 때, 만들어진 직사각형의 넓이는 ab이다. 하나의 막대기는 하나의 직사각형을 만드는 데만 이용할 수 있고, 가능한 많은 직사각형을 만들면서도 직사각형들의 넓이 합이 최대가 되고자 한다. 가지고 있는 막대기의 정보가 주어졌을 때, 만들 수 있는 직사각형들의 넓이 합의 최댓값을 구하시오. 입력 첫째 줄에는 가지고 있는 막대기의 개수 N이 주어진다. 둘째 줄에는 S1, ..., Sn .. 2023. 6. 19.
[python] 구름스퀘어 문제 구름스퀘어의 타운 홀은 다양한 행사를 진행할 수 있는 공간이다. 타운 홀에 N개의 행사가 예정되어 있다. i번째 행사는 시작 시간 Si 와 종료 시간 ei 까지 진행하려고 하고, 행사끼리 진행하는 시간이 서로 겹치지 않게 가장 많은 행사를 여는 것이 목표이다. 행사는 한 번 시작하면 중간에 종료할 수 없다. 그리고 행사가 종료된 후 바로 다음 행사를 진행할 수는 없고, 최소 1의 시간이 지난 뒤에 다른 행사가 시작할 수 있다. 행사의 시작 시간과 종료 시간이 동일한 경우도 있으며, 이는 시작하자마자 종료된 행사라고 할 수 있다. 타운 홀에서 열릴 수 있는 행사의 최대 개수를 출력하시오. 입력 첫째 줄에 행사의 개수 N이 주어진다. 다음 N개의 줄에는 i번째 행사의 시작 시간과 끝 시간을 나타내는 s.. 2023. 6. 19.
[python] 거스름돈 문제 어느 가게에는 1원, 5원, 10원, 20원, 40원 총 5종류의 동전이 있다. 손님에게 N원의 거스름돈을 주려고 한다. N원을 거슬러 주기 위해 필요한 동전의 최소 개수는 몇 개일까? 입력 첫째 줄에 정수 N이 주어진다. 1 ≤ N ≤ 10^9 동전의 개수는 무한하다. import sys input = sys.stdin.readline n = int(input()) coin = 0 for c in [40, 20, 10, 5, 1]: if n // c != 0: coin += n // c n %= c print(coin) 큰 값부터 나누어 나가면 쉽게 해결할 수 있는 문제이다. ※출처 https://multicampus-kdt.goorm.io/lecture/38996/멀티잇-코딩테스트-러닝클래스-p.. 2023. 6. 19.
[python] 1차원 뿌요뿌요 문제 뿌요뿌요는 여러 색깔의 뿌요(블럭)들을 적절히 배치하여, 가능한 많은 뿌요를 터트리는 것이 목적인 낙하형 퍼즐 게임이다. 원래 게임은 2차원 보드에서 진행이 되지만 이 문제는 1차원 보드라고 가정하자. 현재 보드 위에 N개의 뿌요가 늘어선 상태이며, 같은 색깔의 뿌요가 M개 이상 서로 붙어 있으면 터진다. 여러 뿌요가 동시에 터지는 조건을 만족할 때는 그 중 가장 왼쪽에 있는 뿌요들이 터지기 시작한다. 보드의 초기 상태를 나타낸 문자열이 주어졌을 때, 더 이상 뿌요가 터지지 않게 되었을 때 보드의 상태를 구해보자. 예제 설명 처음 보드의 상태는 ABCCBCCDA 이고 2개가 붙어있을 경우 터진다고 가정하자. 처음 뿌요가 터짐에 따라 ABBCCDA, ACCDA, ADA 순서로 보드의 상태가 변하게 된.. 2023. 6. 16.

티스토리툴바