본문 바로가기

프로그래밍/PS

 (80)
[C++] 백준 2805번: 나무 자르기 문제 바로가기 이 문제는 1654번: 랜선 자르기와 비슷하다. 그 때에도 탈출조건 때문에 애를 먹었다. 하지만 그 때 되짚어 봤던 것처럼, HIGH(또는 RIGHT)에는 MID - 1을, LOW(또는 LEFT)에는 MID + 1을 대입하고 while문의 조건을 HIGH ≥ LOW로 하면 무한루프에 빠지지 않는다. 또는 HIGH, LOW = MID로 하되, HIGH > LOW + 1을 while문 조건으로 해도 상관없다. 둘은 사실상 같은거다. 이 문제를 풀면서 이를 잊고 있다가 무한루프로 인한 시간초과가 두 번이나 발생했다. 공식처럼 익혀 놓아야겠다. #include int main() { int N, M, MID; scanf( "%d %d", &N, &M); int LOW = 0; int HIGH = ..
[C++] 백준 15829번: Hashing 1. Small (50점) 서브태스크 Small(50 점)에 대한 해답은 어렵지 않다. 각 문자에 대해서 int 형식으로 변환하여 31를 인덱스만큼 거듭제곱한 것을 곱하고 합한 값을 1234567891로 나눈 나머지를 출력하면 된다. 1 ≤ L ≤ 5일 때는 int로도 충분히 풀 수 있을 정도로 숫자가 크지 않다. #include using namespace std; int pow(int num, int p) { int result = 1; for (int i = 0; i < p; i++) { result *= num; } return result; } int main() { int L; scanf("%d", &L); char* str = new char[L + 1]; scanf("%s", str); i..
[C++] 백준 4949번: 균형잡힌 세상 이 문제는 이전에 풀었던 9012번: 괄호의 응용 문제다. 그 때와 다른 점은 대괄호가 추가 되었다는 점. 그래서 그에 대한 int 값 하나만 더 추가하면 되는거 아닌가?라고 생각했던 건 큰 오산이었다. ([)]이렇게 괄호 안에 불완전한 괄호가 있으면 안 된다. 위와 같은 방법으로는 판독할 수 없다. 하지만 생각할 수 있는 무적의 방법이 있다. 한 쌍을 이루는 괄호가 인접해 있는 경우를 계속 지우다 보면 균형잡힌 문장에서는 결국 모두 없어지지만 균형잡히지 않은 문장에서는 괄호가 남는 것을 알 수 있다. 이를 적용하면 된다. 말은 쉽지만 막상 이를 구현하려니 쉽지 않다. 걸핏하면 메모리 접근 오류가 발생하니 말이다. 단계별로 생각해보자. 1. 입력 이 문제에서 입력은 여러 줄에 걸쳐서 될 수도 있다. 하지..
[C++] 백준 2108번: 통계학 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 이번 문제는 네 가지의 출력을 해야한다. 그래서 각 출력을 작은 목표로 차근차근 풀어 나가면 다가가기 쉬울 것이다. 1. 산술평균 평균은 각 수를 입력받을 때, 입력받은 수를 합한 뒤 N으로 나눠 출력하면 된다. 이 때, 소숫점 아래 첫 번째 자리에서 반올림을 해야하므로 round 함수를 이용하고 int로 캐스팅하여 출력했다. 각 예제에 대한 출력도 옳게 나온다. #include #include using namespace std; int main() { int N; scan..
[C++] 백준 11866번: 요세푸스 문제 0 이 문제는 생각보다 어렵지 않다. 나는 vector를 이용해 1부터 N까지 push_back 하고, count라는 변수를 이용했다. count가 K가 되면 그 때 iterator가 가리키고 있던 요소를 출력하고 해당 요소를 erase한다. 그리고 count는 1이 된다. count가 다시 K가 될 때 까지 iterator는 다음 요소를 가리키고, 마지막 요소인 경우 처음을 가리킨다. #include #include using namespace std; int main() { int N, K; scanf("%d %d", &N, &K); vector P; for (int i = 0; i < N; i++) { P.push_back(i + 1); } int count = 1; printf("\n"); retur..
[C++] 백준 1966번: 프린터 큐 이 문제를 푸는데 조금 오랜 시간이 걸렸다. 왜냐하면 문제의 설명이 다소 이해하기 어려웠기 떄문이다. 처음에 풀었던 방식은 큐 배열을 이용해서 중요도에 따라 다른 큐에 순차적으로 집어넣는 방식으로 했지만, {1, 1, 9, 1, 1, 1}의 경우 0번 인덱스가 3번 인덱스보다 늦게 나와야 하므로 위의 방법은 틀리다. 그래서 리스트를 이용하여 맨 앞 인덱스의 중요도 보다 높은 인덱스가 있는지 스캔하며 있으면 push_back, pop_front를 이용해 문제에 주어진 작동방식대로 구현했다. goto 문을 유용하게 이용한 것 같다. #include #include using namespace std; int main() { int T; scanf("%d", &T); while (T--) { int N, M;..
[C++] 백준 11650번: 좌표 정렬하기 이 문제를 처음 시도할 떄는 크기가 N인 두 개의 배열(X, Y)을 선언하고, X의 값 기준으로 정렬할 때 Y도 같이 바꾸는 방식으로 코드를 짰다. 그러나 예상했던 것처럼 시간초과가 떴다. #include using namespace std; int main() { int N, K; scanf("%d", &N); int* coords_x = new int[N]; int* coords_y = new int[N]; for (int i = 0; i < N; i++) { scanf("%d %d", coords_x + i, coords_y + i); } bool isSorted = false; while (!isSorted) { isSorted = true; for (int i = 1; i < N; i++) { ..
[C++] 백준 2775번: 부녀회장이 될테야 이 문제는 종이에 직접 적어가며 풀면 금방 푼다. 주어진 조건대로 수를 채워나가면 아래와 같은 표를 얻을 수 있다. 피보나치수열과 비슷한 느낌으로 수를 더해나간다. 맨 아래 0층은 1부터 쭉 수를 더해나가고, 각 층의 1호는 1로만 채워나간다. 연산은 1층의 2호부터 오른쪽으로 쭉 나아가며 한 층씩 올라가는데, 문제에서 주어진 것처럼 아래층의 해당 호수까지 숫자를 다 더해나가는 방법도 있지만, 바로 왼쪽과 아래칸의 합으로도 같은 결과를 얻을 수 있다. 바로 왼쪽 칸이 아래칸을 제외한 합이기 때문이다. 이를 활용하여, K와 N이 입력되면 (K + 1) * N의 크기를 갖는 배열을 선언하고 위의 규칙대로 끝까지 채워나간 뒤 마지막 칸의 값을 출력하면 된다. 이때 K + 1인 이유는 0층부터 시작하기 때문이다..

티스토리툴바