문제 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2초 128 MB 20260 8357 6157 41.082% 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 ..

문제 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2초 256 MB 9500 5460 4170 58.650% N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1≤N≤3^7, N은 3^k..

문제 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 된다. 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 된다. 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2 등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축한다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 된다. 위 그림과 같이 16x16크기의 예제 그림은 쿼드 트리가 어떻게 분할해 압축하는지를 보여준다. 이때 전체 그림의 압축 결과는 xxwww bxwxw bbbww xxxww bbbww wwbb가 된다..

문제 지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다. 풀이 이 문제 역시 Z문제와 비슷하게 수학적으로 접근하였다. 우선 숫자가 abcd라고 할때, 역순으로 d c b a로 배열에 저장하였다. (각 숫자의 index가 자릿수랑 같게 해서 생각하기 편하게 할려고.) 그리고 각 자리수마다 숫자를 세어보았다. 근데 0일때는 또 달랐다. 왜냐하면 페이지가 784이면 784이지 0784가 아니기 때문이다. 0일..

문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다. 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을..

문제 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다. 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까? 입력 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N..

문제 4X4 의 격자 형태로 배치된 16개의 시계가 있습니다. 이 시계들은 모두 12시 3시,6시,9시 를 가리키고 있는데, 이 시계들이 모두 12시를 가리키도록 바꾸고 싶습니다. 10개의 스위치를 조작해 이 시계를 3시간 앞으로 당길 수 있는데, 이 스위치들은 아래 표와 같이 연결되어있습니다. 스위치 번호 연결된 시계 스위치 번호 연결된 시계 0 0, 1, 2 5 0, 2, 14, 15 1 3, 7, 9, 11 6 3, 14, 15 2 4, 10, 14, 15 7 4, 5, 7, 14, 15 3 0, 4, 5, 6, 7 8 1, 2, 3, 4, 5 4 6, 7, 8, 10, 12 9 3, 4, 5, 9, 13 입력 테스트 케이스 C (C stackoverflow 에러로 실패. 책을 보고( 0 1 2 3..

문제 H x W 크기의 게임판이 있을때, 검은칸(#)과 흰칸(.)으로 구성되어 있음. 이중 모든 흰 칸을 세칸짜리 L자 모양의 블록으로 덮어야 함. 블록을 돌릴 수 있지만, 겹치거나 칸을 나가면 안됨. 이때 덮는 방법의 수를 계산하는 문제. 입력 테스트 케이스 C(c .) 성공시 cover 하나씩 늘려서 저장. 코드 (JAVA) public class BOARDCOVER { public static StringBuilder sb = new StringBuilder(); public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in)); public static java.ut..