이 문제는 쿼드 트리 이미지 압축 방식의 출력 길이에 관한 문제입니다. L2개의 픽셀로 구성된 L×L 크기의 이미지를 생각해봅시다. 이미지의 픽셀은 0 또는 1로 표현됩니다. (0으로 표현된 픽셀을 0-픽셀, 1로 표현된 픽셀을 1-픽셀이라 부릅시다.)
이때, 쿼드 트리 이미지 압축 방식은 다음과 같습니다.
만약 이미지가 0-픽셀과 1-픽셀로 함께 구성된 경우, 단계(2)를 거칩니다. 이때, 4개의 이미지로 분할됨을 나타내주기 위해 인코딩시 이미지 코드 앞에 1을 붙여줍니다. 그렇지 않으면 전체 이미지를 00 또는 01로 인코딩하여 이미지가 전부 0-픽셀 또는 전부 1-픽셀로만 구성됨을 알려줍니다.
이미지 I를 아래와 같이 크기가 같은 4개의 부분 이미지 A, B, C, D로 분할합니다.그런 다음, 단계(1)을 A, B, C, D의 순서대로 각각 네 개의 부분 이미지에 적용시킵니다.
(I)를 인코딩을 마친 이미지 I라고 합시다. 다음 예제는 이미지를 압축하기 위한 인코딩 과정을 보여줍니다.
예시 1. 이 예시는 4×4크기 이미지의 인코딩 과정입니다.
최종 결과에 30비트(0과 1)가 있으므로 압축 이미지의 길이는 30입니다.
예시 2. 이 예시는 8×8크기 이미지의 인코딩 과정입니다.
따라서 압축 이미지의 길이는 9(비트) 입니다.
입력에서 L×L 크기의 이미지(1≤L≤64, L은 2의 거듭제곱)를 읽습니다.
쿼드 트리 압축 방식으로 인코딩된 압축 이미지의 길이(비트 수)를 계산합니다.
출력에 압축 이미지의 길이를 씁니다.
입력:
L×L 크기의 정사각형 이미지라면, 입력 파일에는 L+1줄이 있습니다. 첫 번째 줄은 정수 L이 주어집니다. 이후 이어지는 L개의 줄에서 각 줄마다 L개의 비트를 입력받습니다. 이때, 인접한 두 비트 사이에 공백이 있습니다.
lighter 4년 전 2
이 문제는 쿼드 트리 이미지 압축 방식의 출력 길이에 관한 문제입니다. L2개의 픽셀로 구성된 L×L 크기의 이미지를 생각해봅시다. 이미지의 픽셀은 0 또는 1로 표현됩니다. (0으로 표현된 픽셀을 0-픽셀, 1로 표현된 픽셀을 1-픽셀이라 부릅시다.)
이때, 쿼드 트리 이미지 압축 방식은 다음과 같습니다.
(I)를 인코딩을 마친 이미지 I라고 합시다. 다음 예제는 이미지를 압축하기 위한 인코딩 과정을 보여줍니다.
예시 1. 이 예시는 4×4크기 이미지의 인코딩 과정입니다.
최종 결과에 30비트(0과 1)가 있으므로 압축 이미지의 길이는 30입니다.
예시 2. 이 예시는 8×8크기 이미지의 인코딩 과정입니다.
따라서 압축 이미지의 길이는 9(비트) 입니다.
입력:
L×L 크기의 정사각형 이미지라면, 입력 파일에는 L+1줄이 있습니다. 첫 번째 줄은 정수 L이 주어집니다. 이후 이어지는 L개의 줄에서 각 줄마다 L개의 비트를 입력받습니다. 이때, 인접한 두 비트 사이에 공백이 있습니다.
출력:
압축 이미지의 길이(비트 수)인 하나의 정수를 출력합니다.