분류 전체보기

[3020] 개똥벌레(C++)

문제 3020번: 개똥벌레 문제 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석�� www.acmicpc.net 해결 방법 1. 석순의 길이는 입력받는 값 그대로 stalagmite 배열에 저장 2. 종유석의 길이는 바닥과 종유석까지의 거리로 변환(동굴의 높이 - 종유석 길이)하여 stalactite 배열에 저장 3. stalagmite, stalactite 배열을 각각 오름차순 정렬 4. 1번째 구간부터 동굴의 높이와 같은 구간까지 탐색하며 해당 구간에서 석순과 종유석과 각각 몇 개씩 만나는지 계산! 이때 lower_bound() 함수를 사용하여 만나는 개수를 바..

[1620] 나는야 포켓몬 마스터 이다솜

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제에 그림과 글이 되게 길게 있는데 실질적으로 문제 푸는데는 없어도 전혀 지장이 없었기 때문에 가져오지 않았는데 궁금하다면 문제 링크를 클릭!🖱 ✍️ 해결 방법 문자를 입력받았으면 포켓몬의 이름이 사전식으로 정렬되어 있는 배열에서 해당 문자를 찾아서 번호를 출력해 줄 것이고, 숫자를 입력받았으면 인덱스를 활용하여 바로 포켓몬의 이름을 출력해주면 된다. 따라서 포켓몬의..

[1920] 수 찾기(C++)

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 해결 방법 1. n개의 정수를 배열 a에 입력받는다. 2. 배열 a를 오름차순으로 정렬한다. 3. 배열 a에 존재하는지 알고싶은 숫자들을 하나씩 입력받으면서 직접 구현한 binsearch 함수를 실행한다. (binsearch 함수는 그냥 일반적인 binary search 함수로 구현하면 된다.) 이 문제에서 핵심은 '시간 초과'가 나지 않도록 하는 것이었다. 처음에는 cin, cout, sort()를 사용하여 코..

cin.tie(NULL) / ios_base::sync_with_stdio(false) 사용시 주의사항

일반적으로 주요 입출력 방법의 속도 차이는 아래 표와 같다. 언어 입력 방법 평균(초) C/C++17 scanf 0.798 C++17 cin 2.1742 C++17 ios_base::sync_with_stdio(false); cin.tie(NULL); 0.5938 C++17 ios_base::sync_with_stdio(false); 0.6348 언어 출력 방법 평균(초) C/C++17 printf 0.8614 C++17 ios_base::sync_with_stdio(false); cout

[10610] 30

https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶� www.acmicpc.net 🔎 해결 방법 우선 30의 배수가 되기 위해서는 두 가지를 만족해야 한다. 일의 자리가 0 각 자리의 합이 3의 배수 따라서 코드도 이런식으로 짜면 된다. ✍️ 알고리즘 1. string으로 문자열을 입력받은 후, sort 함수를 사용해서 오름차순으로 정렬한다. ex) 입력 : 80875542 -> 정렬한 후 : 02455788 2. 문자열의 첫번째 원소가 0인지 확인 0이라면 30의 배수가 되..

[2352] 반도체 설계(C++)

문제 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 🔎 해결 방법 이 문제는 [11053] 가장 긴 증가하는 부분 수열과 같이 왼쪽 포트는 이미 오름차순으로 정렬이 되어 있으므로 이와 연결된 두번째 포트가 어떻게 해야 가장 긴 증가하는 부분 수열을 이루는지를 찾으면 된다. 그래서 처음에는 [11053] 가장 긴 증가하는 부분 수열 문제를 해결한 것과 같이 이중 for문을 사용한 dp로 해결하려고 했다. 하지만 틀렸습니다가 떠서 질문들을 찾아보니 대부분 "LIS" 라는 알고리즘을 사용하여 ..

[11722] 가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 💡 내 코드(C++) // [11722] 가장 긴 감소하는 부분 수열 // https://www.acmicpc.net/problem/11722 // dp #include #include using namespace std; int main(void) { int n; // size of the sequence int dp..

[11055] 가장 큰 증가 부분 수열

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 💡 내 코드(C++) // [11055] 가장 큰 증가 부분 수열 // https://www.acmicpc.net/problem/11055 // dp #include #include using namespace std; int main(void) { int n; // size of the sequence int a[1001], dp[10..