본문 바로가기

전체 글190

[백준] 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 과 같이 바꿀 수 있다. 주어진 문자열을 바꾸는데 필요한 최소 횟수를 출력하면 된다. 풀이 과정 문제를 보고, 가장 먼저 떠올랐던.. 2021. 4. 10.
[백준] 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일을 이용하고 이런 식으로 전.. 2021. 4. 9.
[백준] 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가지 방법을 한 번씩 모두 사용해야 한다.) 풀이 과정 병든나이트는 이동 시, 무조건 오른쪽으로는 이동을 하게 되어있고, 위 아.. 2021. 4. 9.
[백준] 2217 로프 (Python 파이썬) www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 설명 N개의 로프를 이용해 물체를 들어올린다. N개의 로프는 주어진 중량만큼까지만 물체를 들어올릴 수 있으며, K개의 로프를 이용하여 W무게의 물체를 들어올린다면, 모든 로프에 똑같이 W / K 만큼의 중량이 걸리게 된다. 입력으로 각 로프들에 대한 정보가 주어지면, 이 로프들을 이용하여 버틸 수 있는 최대 중량을 출력하면 된다. 풀이 과정 A라는 로프가 버틸 수 있는 중량이 최대 A라면 이 로프.. 2021. 4. 9.
[백준] 13305 주유소 (Python 파이썬) www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 설명 N개의 도시가 일렬로 나열되어 있고, 각 도시간의 거리를 입력받는다. 그리고 그 도시에서의 리터당 주유비를 입력받는다. 이 때, 도시의 시작점에서 끝지점까지 이동하는데 드는 최소의 비용을 구하면 된다. 풀이 과정 각 도시마다 주유소의 가격이 다르기 때문에, 최소의 비용으로 최대충전을 하는 것이 목표다. 이 때, 시작점에서는 반드시 주유가 되어있어야 하기 때문에 첫 최소비용은 시작점의 가.. 2021. 4. 8.
[백준] 1541 잃어버린 괄호 (Python 파이썬) www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 설명 수식이 문자열로 주어질 때, 적절한 괄호를 쳐서 수식의 결과값을 최소로 만들면 된다. 단, 처음과 숫자는 숫자이며, 두 개 이상의 연산자가 나타나지 않으며(++,--) 연산자는 +, -만 사용할 수 있다. 풀이 과정 그리디 알고리즘 문제이다. 최소값을 만들기 위해선 어떻게 해야할까? 마이너스 바로 뒤에 괄호를 열고 그 안의 수식을 최대로 만든 후 다시 괄호를 닫으면 된다. 처음 풀었던 방법은 바.. 2021. 4. 8.

티스토리툴바