백준 18222 - 투에-모스 문자열 시간 제한 1초, 메모리 제한 256MB # 조건 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 _X'_을 만든다. X의 뒤에 _X'_를 붙인 문자열을 X로 다시 정의한다. 2~3의 과정을 무한히 반복한다. 즉, X는 처음에 "0"으로 시작하여 "01"이 되고, "0110"이 되고, "01101001"이 되고, ⋯ 의 과정을 거쳐 다음과 같이 나타내어진다. "011010011001011010010110011010011001011001101001⋯⋯" 자연수 k가 주어졌을 때 X의 k번째에는 무슨 문자가 오는지 구하여라..

백준 12850_본대 산책2 시간 제한 1초, 메모리 제한 512MB # 조건 숭실 대학교 정보 과학관은 유배를 당해서 캠퍼스의 길 건너편에 있다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 꽃 이 활짝 핀 본 대를 선망한다. 어느 날 준영이는 본 대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다. 한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가..

http://wwww.acmicpc.net/problem/13172 # 조건 M개의 주사위가 있어서 이 중 i번째 주사위가 Ni면체 주사위이고 모든 면에 적힌 수를 더한 값이 Si일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다고 가정한 상태에서 모든 주사위를 각각 한 번씩 던졌을 때 나온 수들의 합의 기댓값을 구하는 문제를 만들었다. 확률변수 X의 기댓값을 E(X)로 나타내면, 기댓값의 선형성에 의해서 두 확률변수 X, Y에 대해 E(X + Y) = E(X) + E(Y)가 성립하므로, 이 문제의 답을 아래와 같이 간단하게 나타낼 수 있다. S1/N1 + S2/N2 + ... + SM/NM 즉, 각 주사위에서 나오게 되는 수의 기댓값을 모두 더하면 답이 되는 것이다...

http://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net # 조건 피보나치 수는 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, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을..

http://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net # 조건 크기가 N * N 인 행렬 A가 주어진다. 이 때, A의 B제곱을 구하는 프로그램을 작성 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net # 조건 흑백 영상을 압축하여 표현하는 데이터 구조 쿼드 트리 흰 점을 0, 검은 점을 1로 표현하는 2차원 배열 모두 0으로만 되어 있으면 압축 결과 '0' 모두 1로만 되어 있으면 압축 결과 '1' 섞여 있다면, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 -> 4개의 영상으로 나누어 압축 압축한 결과를 차례대로 괄호 안에 묶어서 표현 2^i 개를 하나로 압축 가능하며 하나로 ..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net # 조건 여러 개의 정사각형 칸들은 하얀색이나 파란색으로 칠해져있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들자. 전체 종이 크기 NxN(N = 2^k) 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 크기가 똑같은 N/2 x N/2 크기의 색종이로 나눈다. 파란색이..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net # 조건 N x N 크기의 행렬로 표현되는 종이 -1, 0, 1 중 하나가 저장 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용 위의 경우가 아닌 경우 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘리 종이에 대해서 위의 과정을 반복 -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구하라 N(1 일치한다면 넘어가고 불일치시 9..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net # 조건 크기가 2^N x 2^N 배열을 Z모양으로 탐색 왼쪽위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 탐색하면 된다. N>1 인 경우, 배열을 크기가 2^(N-1) x 2^(N-1)로 4등분 한 후 재귀적 순서대로 방문 r행 c열을 몇 번쨰로 방문하는지 출력 # 접근 방법 및 Solution 2^(N-1) x 2^(N-1) 로 나눠서 생각 해준다. 결국 1, 2, 3, 4, 분면에 따..