본문 바로가기

Computer Science/Problem Solving17

[BOJ] 2217번: 로프 문제 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 입출력 예시 풀이 풀고 나서 바로 정리했어야 하는데 시간이 좀 지나서 그 당.. 2024. 2. 25.

[BOJ] 14501번: 퇴사 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 $T_{i}$와 상담을 했을 때 받을 수 있는 금액 $P_{i}$로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다. 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. .. 2024. 2. 5.

[BOJ] 2960번: RESETO 문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입출력 예시 풀이 에라토스테네스의 체는 굉장히 유명한 유형임에도 불구하고 볼 때마다 새로운 느낌이다. 풀이를 완전히 외워두던가 해야겠다. 아래는 문제를 보고 내 머릿속에 떠올랐던 생각들이다. ◾ 지워진 숫자가 몇 번째인지 세기 위한 변수가 필요함 → cnt 변수 정의 .. 2024. 1. 18.

[BOJ] 15686번: 치킨 배달 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아래와 같은 지.. 2024. 1. 16.

[BOJ] 1789번: 수들의 합 문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입출력 예시 풀이 입출력이 굉장히 간단하고 solved.ac 기준 티어도 높진 않지만 내 기준 흥미로운 문제여서 정리해둔다. 문제와 예시가 짧긴 했으나 이해하는 데에 오래 걸리지는 않았다. 문제를 보자마자 내 머릿속에 떠오른 생각은 아래와 같다. Step. 1) S를 어떻게 구성할 것인가? N을 최대로 만들기 위해서는 작은 수들부터 고려해야 한다. 즉, 몇 개의 숫자를 더해 200을 만드려고 할 때 99, 101 조합보다는 5, 10, 25, ..., 90과 같은 조합이 좋은 것! Step. 2) 작은 수들부터 고려하는 방법은? 여기서 DP 개념이 살짝 얹어지게 되는데ㅡ 일단 1부터 순서대로 계속 수를 더해.. 2024. 1. 2.

[BOJ] 1475번: 방 번호 문제 다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다. 다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.) 입출력 예시 풀이 처음에 문제랑 입출력 예시 보자마자 금방 풀 줄 알았는데 또 스스로를 과대평가해버린 것이었음. 질문 게시판과 구글링으로 힌트 얻은 후에야 제출할 수 있었다. 힌트 보면 아~ 하는데 그 과정을 내 힘으로 떠올리는 게 왜이렇게 어려울까 🥲 일단 내가 생각해본 풀이 방식들은 아래와 같다. 아이디어 1) 문자열 단순 확인.. 2023. 12. 3.

이전 1 2 3 다음

티스토리툴바