넘치게 채우기

https://www.acmicpc.net/problem/1195BOJ - 킥다운문제 유형: 문자열 처리, 완전 탐색문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제세계적으로 유명한 엄지민 자동차 회사는 효율적인 킥다운 장치를 만들어달라는 의뢰를 받았다. 킥다운이란 자동차에서 낮은 기어로 바꾸는 장치를 의미한다. 연구 끝에 효율적인 킥다운 장치는 '이'와 '홈'이 불규칙하게 배열되어 있는 기어로 만들어져야 한다는 것을 알았다.첫 번째 그림과 같이 두 기어 파트가 서로 마주보고 있게 된다. 튀어나온 것이 기어의 이, 들어간 곳이 홈이다. 그리고 이들을 두 번째 그림과 같이 서로 맞물리게 끼우는 것으로 킥다운 장치를 만들 수 있다. 하지만 문제는 맞물리게 하였을 때 가로 너비가 짧을..

https://www.acmicpc.net/problem/1005BOJ - ACM Craft문제 유형: 위상 정렬문제 난이도: Gold III시간 제한: 1초메모리 제한: 256MB 문제서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자.이번..

https://www.acmicpc.net/problem/1189BOJ - 컴백홈문제 유형: 백트래킹문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f       bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde       a...  abcd  abc.  abcd  a...  a.gh  abc. 거리 :  6     6     6     8     8    10    6위..

https://www.acmicpc.net/problem/1183BOJ - 약속문제 유형: 수학, 정렬문제 난이도: Silver II시간 제한: 2초메모리 제한: 128MB문제마법사 N명이 머글 문화를 이해하기 위해 머글과 약속을 잡았다. 각 마법사는 한 명의 머글을 만날 예정이다. 하지만, 마법사는 약속 시간보다 빨리 또는 늦게 도착할 수 있기 때문에 고민에 빠졌다. 결국 기다리는 시간을 최소화 하기 위해 모든 약속 시간을 T씩 미루려고 한다. 기다리는 시간은 먼저 도착한 사람이 늦게 도착한 사람이 도착할 때까지 기다리는 시간을 의미한다.마법사의 약속 시간은 A1, A2, ..., AN이고, 도착 시간은 B1, B2, ..., BN이다. 약속 시간을 T만큼 미루면, 기다리는 시간의 합은 |Ai + T ..

https://www.acmicpc.net/problem/1182BOJ - 부분수열의 합문제 유형: 브루트포스, 백트래킹, 비트마스킹문제 난이도: Silver II시간 제한: 2초메모리 제한: 256MB 문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 풀이백트래킹 또는 비트마스킹으로 풀 수 있다.백트래킹으로 ..

https://www.acmicpc.net/problem/1141BOJ - 접두사문제 유형: 트라이, 정렬, 그리디문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오. 입력첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 ..

https://www.acmicpc.net/problem/1138BOJ - 줄 세우기문제 유형: 우선순위 큐, 위상 정렬문제 난이도: Silver II시간 제한: 2초메모리 제한: 128MB 문제N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오. 입력첫째 줄에 사람의..

https://www.acmicpc.net/problem/1124BOJ - 언더프라임문제 유형: 수학문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자. 입력첫째 줄에 두 정수 A와 B가 주어진다. 2  출력첫째 줄에 A보다 크거나 같고, B보..

https://www.acmicpc.net/problem/11444BOJ - 피보나치 수 6문제 유형: 피보나치 수, 분할 정복문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n이 주어진다. n은 ..

https://www.acmicpc.net/problem/1105BOJ - 팔문제 유형: 수학, 그리디문제 난이도: Silver I시간 제한: 1초메모리 제한: 512MB 문제L과 R이 주어진다. 이때, L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. 출력첫째 줄에 L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오. 풀이 이 문제에서 중요한 것은, 상위 자릿수에서..