백준 16565 - N포커 시간 제한 1초, 메모리 제한 256MB # 조건 정연이는 트럼프 카드 (Playing Card)로 할 수 있는 새로운 게임을 만들기로 결심했다. 우선 이 게임은 딜러와 플레이어가 1:1로 플레이한다. 그리고 플레이어는 놓여진 52장의 트럼프 카드에서 N장의 카드를 뽑는다. 뽑은 카드들로 "포카드 (four of a kind)" 족보를 만들 수 있다면 플레이어의 승리, 만들 수 없다면 딜러의 승리로 게임이 끝난다. 그러나 정연이는 아직 공정한 게임을 위한, 뽑는 카드의 수 N을 결정하지 못하였다. 정연이가 쉽게 결정을 내릴 수 있도록, N개의 카드를 뽑았을 때 플레이어가 이기는 경우의 수를 출력하는 프로그램을 작성해주자. 트럼프 카드는 다음과 같은 52장의 카드로 구성된다. 포..

백준 15824_너 봄에는 캡사이신이 맛있단다 시간 제한 1초, 메모리 제한 512MB # 조건 '스코빌 지수'란 고추류가 가진 매운맛의 원인인 캡사이신의 농도를 수치화 한 단위이다. 주헌이가 느끼는 매운 정도는 굉장히 독특한데, 먹고 있는 메뉴의 절대 수치가 아닌 음식과의 상대수치에 기반한다. 예를 들어 [5, 2, 8]의 스코빌 지수를 가진 음식을 먹을 때 주헌이가 느끼는 매운 정도는 가장 높은 수치인 8과 가장 낮은 수치인 2의 차이인 6만큼의 매운맛을 느낀다. 이처럼 메뉴들의 스코빌 지수가 있을 때 그 최댓값과 최솟값의 차이를 "주헌고통지수"라고 정의한다. 최근 주헌이에게 좋아하는 매운맛 전문점이 생겼다. 메뉴가 아주 다양한 이 음식점은 모든 메뉴의 스코빌 지수를 명시한 메뉴판을 제공한다. 주헌이..

백준 11689 - GCD(n, k) = 1 시간제한 1초, 메모리 제한 256MB # 조건 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n (1 ≤ n ≤ 10^12)이 주어진다. 출력 GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다. # 접근 방법 n이 주어졌을 때 서로소인 수의 갯수를 구하는 문제이다. 관련된 공식이 있을 것 같아 검색해보니 오일러 피(파이) 함수라는 것이 존재하였다. 아래 식과 같이 구할 수 있으며 핵심 성질은 주어진 n의 소인수를 구한 뒤, 각 소인수들의 (1-1/p)를 구하여 n에 곱해주면 서로소의 갯수를 구할 수 있다. 이 때, 모든 수에..

백준 27172_수 나누기 게임 시간 제한 1초, 메모리 제한 1024MB # 조건 보드게임컵을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 수 나누기 게임을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. 게임을 시작하기 전 각 플레이어는 1부터 1,000,000사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다. 매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다. 결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지가 0$0$이면 승리합니다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어 떨어지면 패배합니다. 둘 다 아니라..

백준 1019_책 페이지 시간 제한 2초, 메모리 제한 128MB # 조건 지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자. 입력 첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. # 접근 방법 10억이므로 우선 브루트포스로는 시간초과가 발생하므로 풀 수 없다. 따라서 규칙을 찾아야 되는데 시간이 상당히 오래 걸렸다.. 찾은 규칙 설명 0~9까지는 앞자리가 변경되도 1개씩 나온다. 이걸 이용해서, 전체 숫자에서 일..

백준 9527 - 1의 개수 세기 시간 제한 1초, 메모리 제한 128MB # 조건 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자. 입력 첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10^16) 출력 1의 개수를 세어 출력한다. # 접근 방법 처음에 어떻게 풀어야 될지 감이 잘 오지 않았던 문제이다. 1000조까지의 범위가 주어지므로 무식하게 풀 수 없었기에 규칙을 찾는데 집중하였다. 2가지 규칙을 찾을 수 있었는데 우선, 1부터 해당 숫자들을 2진수로 변경 시, 2^n -1 까지의..

백준 2163_초콜릿 자르기 # 조건 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 같이 초콜릿을 쪼개면 초콜릿은 두 개의 조각으로 나눠지게 된다. 이제 다시 이 중에서 초콜릿 조각을 하나 들고, 쪼개는 과정을 반복하면 된다. 초콜릿을 쪼개다보면 초콜릿이 녹을 수 있기 때문에, 정화는 가급적이면 초콜..

백준 1011_Fly me to the Alpha Centauri 시간 제한 2초, 메모리 제한 512MB # 조건 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는..

백준 2460_지능형 기차2 시간 제한 1초, 메모리 제한 128MB # 조건 최근에 개발된 지능형 기차가 1번역(출발역)부터 10번역(종착역)까지 10개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. 이 장치를 이용하여 출발역에서 종착역까지 가는 도중 기차 안에 사람이 가장 많을 때의 사람 수를 계산하려고 한다. 단, 이 기차를 이용하는 사람들은 질서 의식이 투철하여, 역에서 기차에 탈 때, 내릴 사람이 모두 내린 후에 기차에 탄다고 가정한다. 예를 들어, 위와 같은 경우를 살펴보자. 이 경우, 기차 안에 사람이 가장 많은 때는 2번역에서 3명의 사람이 기차에서 내리고, 13명의 사람이 기차에 탔을 때로, 총 42명의 사람이 기차 ..