본문 바로가기

프로그래밍/PS

 (80)
[C++] 백준 2869번: 달팽이는 올라가고 싶다 처음에는 이 문제를 시뮬레이션 해가며 답을 구하려고 했다. 아래처럼. #include using namespace std; int main() { long long A, B, V; scanf("%lld %lld %lld", &A, &B, &V); long long day = 1; long long H = 0; while (true) { H += A; if (H >= V) break; H -= B; day++; } printf("%lld\n", day); return 0; } 그러나 입력이 최대 10억까지 주어지고, 시간제한이 0.15초이므로 위의 코드는 시간초과가 발생한다. 그래서 식을 생각해야 하는데, 처음 생각해낸게 다음과 같다. (N - 1) (A - B) + A ≥ V 위에서 N은 나무 막대를 모..
[C++] 백준 10989번: 수 정렬하기3 이번 문제를 algoritm을 include하여 qsort 내장 함수를 이용하고자 하면 시간초과, 메모리초과가 발생한다. 입력되는 값의 개수가 무려 10,000,000개가 될 수 있기 때문이다. 어떻게 해야할지 감도 안 잡히다가, 질문 검색 탭에서 힌트를 얻었다. 카운팅 정렬을 이용하면 메모리 초과를 해결할 수 있다고 한다. 문제를 다시보니, 값의 최대값이 10,000으로 제한돼 있다. 카운팅 정렬에서는 각 값이 몇 번씩 등장했는지 세어준 다음에 값 * 카운트를 새로운 배열에 저장하여 인덱스로 활용한다. 하지만 여기서는 새로운 배열에 저장하려고 하다가는 메모리 초과가 뜨기 떄문에, 카운트만을 활용했다. 처음에 크기가 10,000인 int 배열을 선언한 후 각 값이 입력되면 바로바로 카운트했다. 이후, 카..
[C++] 백준 2798번: 블랙잭 이 문제의 제목을 봤을 때, 뭔가 어렵겠구나 라고 느꼈지만 생각보다 어렵지 않다. 풀이는 간단하다. 모든 경우를 싹 조사하면 된다. 경우의 수도 얼마 안 된다. N이 최대 100인 것을 고려했을 때 입력된 카드들 중 3장을 뽑아서 합을 구하는 모든 수는 조합에서 배웠다시피 100 * 99 * 98 = 970,200밖에 되지 않는다. 1GHz의 CPU에서 연산하는데 9ms밖에 걸리지 않는다. 각 합을 담을 배열도 용량이 크지 않다. 970,200 * 4(byte) = 3,880,800 byte ≒ 3.7 MB 밖에 되지 않는다. 그래서 마음놓고 for문을 3번 중첩하여 모든 경우를 계산하고 int count = 0; for (int i = 0; i < N - 2; i++) { for (int j = i +..
[C++] 백준 10250번: ACM 호텔 #include int main() { int T, H, W, N; scanf("%d", &T); while (T--) { scanf("%d %d %d", &H, &W, &N); for (int w = 1; w
[C++] 백준 1929번: 소수 구하기 이번 문제는 입력이 최대 1,000,000까지다. 연산량이 적지 않은 만큼 입력에서도 신경을 써야 한다. iostream을 이용할 경우 다음을 main 함수 아래에 추가하면 출력이 빨라진다. ios_base::sync_with_stdio(false) 하지만 나는 printf/scanf를 사용하는 것을 선호한다. 이 문제를 풀고자할 때 제일 먼저 떠올리는 해결 방법이 아래 1번 방법이다. 1. M부터 N까지의 각 수에 대해 검사 #include int main() { int M, N; scanf("%d %d", &M, &N); for (int i = M; i
[C++] 백준 9012번: 괄호 이번 문제에서는 주어진 문자열에서 괄호의 세트가 잘 맞춰져 있는가를 검증해야 한다. 즉, 닫힌 괄호로 시작하거나 열린 괄호로 끝나면 "NO"를 출력해야 한다. 그 외에도 닫힌 괄호가 충분하지 않거나 그 반대의 경우도 있겠다. 이런 경우를 하나하나 생각하기엔 복잡하니, 다음과 같이 생각을 간소화 할 있다. 열린괄호는 +1, 닫힌괄호는 -1로 생각하는거다. 처음에는 0으로 시작하여 문자열을 처음부터 스캔해 나간다. 만약 그 과정에서 음수가 되면 명백하게 "NO"다. 왜냐하면 닫힌 괄호가 앞에서 더 많이 나왔기 때문이다. "(()))"이런 경우다. 스캔이 다 끝나면 다시 0으로 돌아와야 한다. +1과 -1의 쌍이 하나씩 매칭되기 떄문이다. 만약 0이 아니면 "NO", 0이면 "YES"다. #include us..
[C++] 백준 2839번 : 설탕배달 입력의 첫 줄에서 배달해야 되는 설탕의 양 N 킬로그램이 주어진다. 설탕을 나눠 담을 수 있는 단위는 5 킬로그램과 3킬로그램으로 제한돼 있다. 여기서 더 적은 갯수의 봉지로 나눠 담아 가려면, 5 킬로그램 봉지의 비중을 최대한 많게 해야한다. #include using namespace std; int main() { int N; scanf("%d", &N); int A = 0; for (int i = 0; 5 * i
[C++] 백준 1654번: 탈출 조건에 대하여 #include using namespace std; int main() { int K, N; scanf("%d %d", &K, &N); int* LANs = new int[K]; long long MAX = 1; for (int i = 0; i MAX) MAX = LANs[i]; } long long MIN = 1; long long MID; while (MAX >= MIN) { MID = (MIN + MAX) / 2; long long P = 0; for (int i = 0; i < K; i++) { P += LANs[i] / MID; } if (P < N) { MAX = MID - 1; } else { MIN =..

티스토리툴바