잡담연구소

www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net IDEA 옛날에 비슷한 문제를 풀었어서 기억이 생생하다. 원형 큐였나 그런 걸 사용하면 된다했는데 그런 건 모른다. 그냥 오로지 큐로 풀었다. 순서를 세면서 내가 원하는 순서가 아니라면 pop한 후 push해서 뒤로 보내버리면 된다. 1번부터 시작이기떄문에 count = 1로 설정해둔다. 1. 내가 원하는 순서가 아닌 경우 front값을 저장한 후 pop , push를 통해 뒤로 보내버린다. count번째 사람이기에 그 다음 사람을 위해 count를 하나 세준다. 2. 내가 원하는 순서인 경우 ..

www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net IDEA 그냥 POP과 PUSH를 카드 1장만 남을 때까지 반복하면 되는 문제다. 아래 두가지만 반복하면 된다. 제일 위에 있는 카드를 바닥에 버린다. -> pop한다 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. -> front를 따로 저장해 둔 후 pop한다. 저장해둔 값을 push한다. #include #include using namespace std; int main() { int n;..

문제를 풀자마자 바로 글을 써야겠다. 기억이 잘 안난다. www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net IDEA 9012 괄호 ( www.acmicpc.net/problem/9012 )와 같다. 몇 번 문장을 받는다와 같은 테스트케이스 갯수가 없다. 온점이 입력될 때까지 문장을 받아야한다. while문 내에서 getline을 통해 한 줄을 string으로 통으로 받고 인덱스를 하나하나 옮겨가며 본다. 길이가 1이면서 .하나 뿐이라면 break..

www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net IDEA 1 : 1 로 비교하며 자신보다 덩치가 큰 사람이 몇 명인지 구해야 자신의 등수가 나오는 문제라고 생각을 했다. 등수는 자신보다 큰 사람에 의해 결정되기 때문에 1, 2, 2, 2, 5 등과 같이 3,4등이 안나올 수 있다. 그래서 정렬은 안되고 1:1 즉 $N^{2}$번 계산해야된다. 전체 사람의 수가 50밖에 되지 않아 최악의 경우에도 2500번 연산 밖에 안돼 그냥 이중 FOR문을 사용..

www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다. 합이 M을 넘지 않는 카드 3장을 찾을 수 있 www.acmicpc.net IDEA 3중 for문을 사용하면 카드의 개수가 100개뿐이기에 최악의 경우에도 1000000 정도밖에 안된다. 투포인터(??)처럼 생각했다. 정렬을 한 이후 i, j, k 세 카드의 합이 블랙잭의 한도인 m을 넘어가는 경우 어차피 그 이후를 탐색해봤자 계속 m을 넘을테니 break를 걸어주어 다음 카드 조합으로 넘어가게 해주었다. ex ) 1 3 5 7 8 m = 10 i =..

www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net IDEA 맨 처음에는 ABC라는 숫자면 분해합이 ABC + A + B + C 즉 2C + 11B + 101A 라는 점에서 어떤 수식을 도출할 수 있을 줄 알았는데 곰곰히 생각해보면 어림도 없을 거 같다. 1부터 주어진 숫자까지 하나하나 분해합을 구해서 비교하는 방식을 생각해보았는데, 어차피 가장 큰 수인 1,000,000이 들어와도 1초에 1억번이니까 충분히 연산을 할 수 있을 거라..