https://www.acmicpc.net/problem/1992 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 10660 6114 4794 57.420% 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 ..

문제 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음 그림은 N=3일 때의 예이다. 입력 첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다 출력..

문제 지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다. 나의 답 알고리즘 첫번째 코드 예시를 많이 얻기 위해 전체 경우의 수 구하는 가장 간단한 알고리즘 먼저 구현 n_list = list() for z in range(0,1): n_list.append(int(input())) for n in n_list: num_result = [0,0,0,0,0,0,0,0,0,0] for i in range(1,..

https://www.acmicpc.net/problem/4811 문제 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다. 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다. 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인..

6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중) 문제 4x4 격자 형태로 배치된 열여섯 개의 시계가 있습니다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있는데, 이 시계들이 모두 12시를 가리키도록 바꾸고 싶습니다. 시계의 시간을 조작하는 유일한 방법은 열 개의 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 세 개에서 많게는 다섯 개의 시계에 연결되어 있습니다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직입니다. (12시일때는 3시로, 3시=>6시, 6시 =>9시, 9시=>12시) 스위치들과 그들이 연결된 시계들의 목록이 주어지고 현재 가리키는 시간들이 주어졌을 때 모든 시계를 12시로 돌리기 위해 최소한 ..

6.5 문제 : 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하) 문제 H X W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 세 칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 다음 그림은 한 게임판과 이를 덮는 방법을 보여줍니다. 게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요. 시간 및 메모리 제한 프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야만 합니다. 입력 입력의 첫 줄에는 테스트 케이스의 수 C(C=0 and tmp[0]=0 and tmp[1]=0 ..

https://www.acmicpc.net/problem/2839 나의 답 # 백준 2839번 : 설탕 배달 # 2020-02-01 num = int(input()) count = 0 while num>=3 : if not(num%5) : # 5의 배수이면 count+= num/5 break else : count+=1 num-=3 if num==1 or num==2: count = -1 else : count += 0 print(int(count)) 분석 다이나믹 알고리즘 앞선 2문제의 영향으로 처음에는 모든 경우의 수를 찾아볼까 생각했다. 하지만 이전 문제와 달리 수의 범위가 확연히 커진데다가 연산의 시간이 너무 오래걸릴 것 같아서 이러한 방식은 아닐 거라고 결론 내렸다. 경우의 수 (특징 찾기) 그..

문제 : 백준 9095번 _ 1,2,3 더하기 https://www.acmicpc.net/problem/9095 나의 답 # 백준 9095번: 1,2,3 더하기 # 2020-02-01 case = int(input()) # 입력받기 num = [] def cpt_num(n): if n>3: # 3보다 크면 return cpt_num(n-3) + cpt_num(n-2) + cpt_num(n-1) elif n==3: # 3이면 return 4 elif n==2: # 2이면 return 2 elif n==1: # 1이면 return 1 while case : case-=1 num.append(int(input())) for n in num: print(cpt_num(n)) 어제 배웠던 다이나믹 프로그래밍을 활..