본문 바로가기

전체 글

[백준] 1449 수리공 항승 (Python 파이썬) www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 문제 설명 수리공이 물이 새는 파이프를 테이프로 수리한다. 테이프는 무한 개 갖고 있으며, 최소한의 테이프를 사용하여 수리해야 한다. 물이 새는곳을 막을 때, 그 위치의 좌우로 0.5만큼씩을 더 막아줘야 물이 새지 않는다. 테이프는 자를 수 없으며, 겹칠수는 있다. 또, 물이 새는 곳의 위치는 자연수이다. 풀이 과정 최소한의 개수로 최대의 이익을 취해야 하는 그리디 알고리즘 문제이다. 먼저 테이.. 더보기
[백준] 1439 뒤집기 (Python 파이썬) www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 문제 설명 0과 1로만 이루어진 문자열 S이 주어진다. 이 문자열S을 모두 같은 숫자로 이루어진 문자열로 바꾸려고 하는데, 연속된 하나 이상의 숫자를 뒤집을 수 있다. (0을 1로, 1을 0로) 예를 들어, 1001001이 있으면 1001001 -> 1111001 -> 1111111 과 같이 바꿀 수 있다. 주어진 문자열을 바꾸는데 필요한 최소 횟수를 출력하면 된다. 풀이 과정 문제를 보고, 가장 먼저 떠올랐던.. 더보기
[백준] 4796 캠핑 (Python 파이썬) www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 문제 설명 입력으로 L, P, V를 입력받는다. ( 1 < L < P < V ) 이는 총 V일간의 휴가기간동안 캠핑장을 연속하는 P일 중, L일동안 이용할 수 있다는 뜻이다. 예를 들어, V = 20, P = 8, L = 5 이면, 총 휴가기간 20일 중 캠핑장을 연속하는 8일중 5일간 이용할 수 있다는 뜻이다. 그래서 처음 5일을 이용하고 그 뒤 3일은 이용을 못하고 다시 5일을 이용하고 이런 식으로 전.. 더보기
[백준] 1783 병든 나이트 (Python 파이썬) www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 병든 나이트는 보통 체스의 나이트와는 다르게 아래의 네가지 방법으로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 이 때, 맵의 크기가 N * M으로 주어질 때, 병든 나이프가 방문할 수 있는 칸의 최대 개수를 구하면 된다. (단, 이동 횟수가 4번 이상이라면, 4가지 방법을 한 번씩 모두 사용해야 한다.) 풀이 과정 병든나이트는 이동 시, 무조건 오른쪽으로는 이동을 하게 되어있고, 위 아.. 더보기
[백준] 2217 로프 (Python 파이썬) www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 설명 N개의 로프를 이용해 물체를 들어올린다. N개의 로프는 주어진 중량만큼까지만 물체를 들어올릴 수 있으며, K개의 로프를 이용하여 W무게의 물체를 들어올린다면, 모든 로프에 똑같이 W / K 만큼의 중량이 걸리게 된다. 입력으로 각 로프들에 대한 정보가 주어지면, 이 로프들을 이용하여 버틸 수 있는 최대 중량을 출력하면 된다. 풀이 과정 A라는 로프가 버틸 수 있는 중량이 최대 A라면 이 로프.. 더보기
[백준] 13305 주유소 (Python 파이썬) www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 설명 N개의 도시가 일렬로 나열되어 있고, 각 도시간의 거리를 입력받는다. 그리고 그 도시에서의 리터당 주유비를 입력받는다. 이 때, 도시의 시작점에서 끝지점까지 이동하는데 드는 최소의 비용을 구하면 된다. 풀이 과정 각 도시마다 주유소의 가격이 다르기 때문에, 최소의 비용으로 최대충전을 하는 것이 목표다. 이 때, 시작점에서는 반드시 주유가 되어있어야 하기 때문에 첫 최소비용은 시작점의 가.. 더보기
[백준] 1541 잃어버린 괄호 (Python 파이썬) www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 설명 수식이 문자열로 주어질 때, 적절한 괄호를 쳐서 수식의 결과값을 최소로 만들면 된다. 단, 처음과 숫자는 숫자이며, 두 개 이상의 연산자가 나타나지 않으며(++,--) 연산자는 +, -만 사용할 수 있다. 풀이 과정 그리디 알고리즘 문제이다. 최소값을 만들기 위해선 어떻게 해야할까? 마이너스 바로 뒤에 괄호를 열고 그 안의 수식을 최대로 만든 후 다시 괄호를 닫으면 된다. 처음 풀었던 방법은 바.. 더보기
[백준] 11399 ATM (Python 파이썬) www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 설명 ATM기 앞에 사람이 N명 서있는데, 이 N명의 사람들이 돈을 인출하는데 걸리는 시간은 제각각이다. 이 때, 앞 사람의 돈을 뽑는 시간이 길 수록, 뒤에 있는 사람들의 대기 시간은 길어지게 된다. 각 사람이 돈을 인출하는데 필요한 시간(대기시간+뽑는시간)의 합의 최솟값을 구하면 된다. 풀이 과정 내가 ATM기에 줄을 서 있다고 가정해보자. 나의 대기시간이 짧아지려면 어떤 상황이 되어야 하는가? 당연히 내 앞에서 돈을 뽑는 사람들이.. 더보기

티스토리툴바