티스토리 뷰
백준 온라인 저지(BOJ) 2164번 카드2
https://www.acmicpc.net/problem/2164
2164번: 카드2
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가
www.acmicpc.net
* 사용언어 : C언어, C++
1. 문제
1부터 N까지 번호의 카드가 위에서 아래로 순서대로 놓여있음
제일 위 카드를 버리고, 그 다음 제일 위 카드를 제일 아래로 옮기는 동작을 반복했을 때
마지막으로 남은 한 장의 번호를 출력
2. 풀이
FIFO(First In First Out)인 큐를 구현하면 풀 수 있는 문제입니다.
개인적으로 Linked List로 값을 실제로 넣고 빼는 방식보다는
넉넉한 크기의 배열을 만들고 head와 tail을 배열의 index로 보고 증가시키는 방식을 선호합니다.
메모리 공간이 넉넉하게 주어진 문제라면 이 방식을 사용하는 것이
구동 시간 절약에 큰 도움이 되니 참고하시길 바랍니다.
(pop을 했을 때 특별한 조치 없이 head만 1 증가시키면 됨, push도 배열의 ++tail 자리에 넣어주면 됨)
다만 이 방식은 배열의 크기를 잘 선언하는 것이 중요합니다.
이 문제는 N이 최대 500,000이고 절반이 버려지고 절반은 다시 push되는 방식입니다.
따라서 필요한 배열의 최대 크기는 500,000 + 250,000 + 125,000 + 62,500 + ... 이므로
무한 등비수열 합 공식에 의해 500,000 / (1 - 1/2) = 1,000,000이 됩니다.
3. 코드
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
18258_카드2
5016KB 4ms
*/
#include <cstdio>
const int LM = 1000000;
int q[LM], h, t = -1, N;
int main() {
#ifdef _WIN32
freopen("input.txt", "r", stdin);
#endif // _WIN32
scanf("%d", &N);
for (int i = 1; i <= N; ++i) q[++t] = i;
while (h < t) {
++h;
q[++t] = q[h++];
}
printf("%d\n", q[t]);
return 0;
}
'개발자 > 문제풀이 (C언어)' 카테고리의 다른 글
[백준/BOJ] 28279번 덱 2 (C/C++) (0) | 2023.12.13 |
---|---|
[백준/BOJ] 11866번 요세푸스 문제 0 (C/C++) (0) | 2023.12.03 |
[백준/BOJ] 18258번 큐 2 (C/C++) (0) | 2023.11.17 |
[백준/BOJ] 12789번 도키도키 간식드리미 (C/C++) (0) | 2023.11.16 |
[백준/BOJ] 4949번 균형잡힌 세상 (C/C++) (0) | 2023.11.16 |
- Total
- Today
- Yesterday
- 유연함의힘
- 나의첫죽음학수업
- 당신도느리게나이들수있습니다
- 알고리즘
- 쿠프마케팅
- 영화감상평
- JUNGOL
- 인간본성불패의법칙
- 최재천의공부
- 세상을 읽는 새로운 언어 빅데이터
- 자동차보험
- 자료구조
- 독서감상평
- 동탄에듀센터2
- 동탄에듀센터
- 센터독서클럽
- 정세현의통찰
- AdSendse
- 시대예보
- 긴 자리 곱셈
- 여가포인트
- 문현공
- 삼성전자
- 관계가상처가되기전에
- 긴 자리 덧셈 뺄셈
- 이용제한
- 독서 감상평
- 나는늘잘해야한다고생각한다
- 호암의마지막꿈
- 정올
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |