[C++] 백준 1541: 잃어버린 괄호 🥈실버 2 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 접근 1. -가 나타나기 전까지는 모든 값을 그냥 더해두고, - 이후의 숫자들은 모두 뺄셈처리 한다. 괄호를 한번 친다고 가정할 때, - 이후에 모든 값을 괄호로 묶는 것이 가장 최솟값이 나오는 방법이기 때문이다. 55-50+40 -> 55-(50+40) -> 55 - 50 - 40 해결방법은 찾았으나 구현을 어떻게 할지가 고민이었다. 1...
[c++] 백준 20365: 블로그2 🥈실버 3 https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 접근 빨간색, 혹은 파란색으로 전체를 칠해놓고, 나머지 색으로 다른 색상이 필요한 부분을 칠해주는 것이 최소의 값이 된다. 문제는 어떤 색으로 전체를 칠할 것이냐였다. 두 색중에 더 많은 색이 나타나는 것을 바탕색으로 칠하고, 더 적게 나타나는 색으로 나머지 부분을 칠하는 것이 최소가 될 것이라고 판단했다. 1. 입력값에서 R과 B의 개수를 알아낸..
[c++] 백준 20300: 서강근육맨 🥈실버 3 https://www.acmicpc.net/problem/20300 20300번: 서강근육맨 PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다. www.acmicpc.net 접근 N이 짝수일 때와 홀수일 때를 구분해서 코드를 작성해야 한다. 먼저, 입력받은 값을 내림차순으로 정렬시켜보자. 5 4 3 2 1 9개의 운동기구가 있는 경우에도 PT를 5번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다. N이 홀수인 경우에는, 가장 먼저 오는 운동기구는 반드시 하나만 사용해야 한다. 5를 따로 때놓고, 나머지 4 3 2 1의 경우..
[c++] 백준 13305: 주유소 🥈실버 3 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 접근 원 안의 숫자가 리터 당 기름의 가격, 막대 위의 숫자가 다음 도시까지의 거리일 때, 맨 오른쪽 도시까지 가기 위한 최소 비용을 출력하는 문제. 5원짜리 도시에서는 다음 도시까지 필요한 거리만큼만 기름을 사는 것이 합리적이다. 다음 도시에서는 리터 당 기름의 가격이 2원밖에 하지 않기 때문이다. > 5 * 2 = 10 만약 2원짜리..
[c++] 백준 11399: ATM 🥈실버 4 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이1 P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2인 경우에서 줄을 [2, 5, 1, 4, 3]으로 세우면 각각의 값은 [1, 2, 3, 3, 4]이다. 이는 그냥 입력 받은 값을 오름차순으로 정렬하라는 것이다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 다음과 같다. 1번사람: 1 2번사람: 1+2 3번사람: 1+2+3 4번사람: 1+2+3+3 5번사..
[c++] 백준 1758: 알바생 강호 🥈실버 4 https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다. 각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다. 접근 돈을 많이 주려고 한 사람이 앞에 설 수록 강호가 받을 수 있는 팁의 액수가 ..
[c++] 백준 2217: 로프 🥈실버 4 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 접근 중량이 어쨌든 간에 중요한 것은 두가지이다. 1. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개만 골라도 된다. 2. 각각의 로프에는 모두 고르게 w/k 만큼의 중량만 걸린다. 예제 입력1을 그림으로 나타내면 다음과 같다. 위의 경우에는 다음과 같은 경우의 수로 물체를 들어올릴 수 있다. 1. 15kg 로프 하나로 든다. > 15 ..
[c++] 백준 1343 : 폴리오미노 🥈실버 5 https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 접근 입력값을 순회하면서 X를 만나면 count 변수를 1씩 증가시킨다. XX를 처리해야 하는 경우는 크게 두가지가 있다. 1. XX 다음 X가 오지 않을때(.이 오거나 맨 끝의 경우) -> AAAA가 들어갈 때까지 더 기다릴 필요가 없으므로 BB를 박는다. 2. XX 다음 X가 올 때 -> 더 기다리면 AAAA를 박을 수 있으므로 처리하지 않는다. 이렇게 진행하다가 count가 4가 되면 AAAA를 박는다. .이 오는 경우의 처리 count가 홀수가..
[c++] 백준 21919 : 소수 최소 공배수 🥈실버 3 https://www.acmicpc.net/problem/21919 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net 접근 에라토스테네스의 체를 활용하여 문제에서 제시한 최대치의 값까지 소수를 판별한다. 제한 수가 1,000,000이므로 long long으로 자료형을 선언하지 않으면 오답처리가 된다. 입력 값들 중에 소수로 판별되는 것들을 벡터에 집어 넣는다. 벡터가 비어있는 경우 소수가 없던 것이므로 -1을 출력한다. 3개 이상의 수에서 최소공배수를 계산하는 법 A, B, C, D.. 이렇게 복수의 수가 있는 경우, A, B의 최소공배수를 먼저 구한다. 그렇게 나온 값과 C의 최소공배수를 구한..
[c++] 백준 2075 : N번째 큰 수 🥈실버 2 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 접근 메모리 제한이 있는 문제라 최대한 적은 공간을 활용해야 한다. 처음엔 그냥 N^2개의 값을 입력받고 우선순위 큐에 다 때려넣으면 최대힙으로 내림차순 정렬될 것이기 때문이므로 N-1만큼 pop하여 N번째 값을 가져오려는 시도를 했는데 시간초과가 나거나 메모리 초과 에러가 발생했다. 대안으로, 우선순위 큐를 사용하되 N^2개가 아니라 N개만 사용하는..
[c++] 백준 11286 : 절댓값 힙 🥈실버 1 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 접근 우선순위 큐를 활용하여 풀이하는 문제입니다. priority_queue : 우선순위가 높은 것 부터 먼저 pop됨, cmp(나중에 출력하고 싶은 것, 먼저 출력하고 싶은 것) = true가 되게 하면 됩니다. 임의로 만든 비교함수를 활용할 경우, 두 요소의 비교에 대한 return 값이 true가 되면 두 값의 순서가 ..
[c++] 백준 1620 : 나는야 포켓몬 마스터 이다솜 🥈실버 4 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 접근 이름으로 번호를 , 번호로 이름을 뽑아내야 한다. 각각의 경우에 해당하는 map을 두개 만들거나, string -> int map과 string 배열을 활용하는 방법으로 구현할 수 있다. 입력값은 정수 또는 문자열이 될 수 있기에, c++에서는 string형으로 문자열을 받아 이것이 정수인지 문자..
