본문 바로가기

PS/Baekjoon Online Judge601

[백준 31235] 올라올라 [C/C++, Python] 문제 길이가 N인 수열 A가 주어질 때, N 이하의 양의 정수 k에 대하여 길이가 N - k + 1인 수열 B를 다음과 같이 정의하자. 수열 B가 감소하지 않도록 하는 k의 최솟값을 구해보자. 예를 들어 A = {3,1,4,2,5}이고 k = 2라면, B = {3,4,4,5}이므로 감소하지 않지만, k = 1이라면 B = {3,1,4,2,5}이므로 감소하는 부분이 존재한다. 이 경우 k의 최솟값은 2이다. 입력 첫째 줄에 수열 A의 길이 N이 주어진다. (1 2024. 1. 16.
[백준 01439] 뒤집기 [C/C++] 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오. 입력 첫째 줄에 문자열 .. 2024. 1. 14.
[백준 13305] 주유소 [C/C++] 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다. 예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는.. 2024. 1. 13.
[백준 01789] 수들의 합 [C/C++] 문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 풀이 S를 최대한 많은 자연수로 이루는 방법이 N의 최댓값을 구할 수 있는 Greedy문제다. S의 범위는 unsigned int인 점에 유의하자. 서로 다른 N개의 자연수로 구성되므로 자연수(num) 1을 1씩 증가시키며 S가 0미만이 되기까지 감산하면 된다. S에서 감산한 num은 loop마지막에 1증가 후 조건식을 통해 중단되므로 num - 1이 N의 최댓값이 된다. 소스코드 보기 출처 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주.. 2024. 1. 12.
[백준 02217] 로프 [C/C++] 문제 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 입력 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수.. 2024. 1. 11.
[백준 05585] 거스름돈 [C/C++] 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다. 출력 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오. 풀이 카운터에 이미 낸 1,000엔에 대해 지불할 금액을 제외하고, 돌려받을 잔돈의 최소 매수를 구하는 문제이다. 잔돈들은 모두 배수이기 때문에, 가장 큰 잔돈부터 빼주면 된다. 돌려받을 잔돈이.. 2024. 1. 10.

티스토리툴바