[c++] 백준 2217: 로프

[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 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2023. 4. 8.
• textsms

[c++] 백준 1343 : 폴리오미노

[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가 홀수가..

• format_list_bulleted 알고리즘 문제 풀이
• · 2023. 4. 6.
• textsms

[c++] 백준 21919 : 소수 최소 공배수

[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의 최소공배수를 구한..

• format_list_bulleted 알고리즘 문제 풀이
• · 2023. 4. 6.
• textsms

[c++] 백준 2075 : N번째 큰 수

[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개만 사용하는..

• format_list_bulleted 알고리즘 문제 풀이
• · 2023. 4. 4.
• textsms

[c++] 백준 11286 : 절댓값 힙

[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가 되면 두 값의 순서가 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2023. 4. 3.
• textsms

[c++] 백준 1620 : 나는야 포켓몬 마스터 이다솜

[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형으로 문자열을 받아 이것이 정수인지 문자..

• format_list_bulleted 알고리즘 문제 풀이
• · 2023. 4. 2.
• textsms