CodeAngie

문제 5*3 개의 전구를 통해 0~9까지의 숫자를 표현할 수 있을 때, 전구가 망가졌을 수도 있음을 가정하고, 켜진 전구들을 살펴보아 만들 수 있는 숫자들의 평균을 구하는 문제이다. 층 안내판의 크기는 5*3 판을 여러 개 이어 붙인 형태이며 판 사이의 꺼진 전구가 존재한다. 풀이 먼저 문제에서 주어진 0~9까지의 표현을 가지고 5*3 판 위의 어떤 전구가 켜졌을 때 어떤 숫자를 만들 수 있는지 판별해야 한다. 예를 들어 5*3 판을 기준으로 (0,0) 위치의 전구가 켜지면 만들 수 있는 숫자들(0,2,3,4,5,6,7,8,9)을 저장한다. 같은 간격으로 숫자가 있기에 (i, j+k*4)를 통해 동일한 위치의 전구들을 확인할 수 있다. 각각의 판이 만들 수 있는 숫자들을 추출한다. 만약 (3,0) 위치의..

문제 x와 k가 주어졌을 때, 다음 식을 만족하는 k번째 y를 구하는 문제이다. x + y = x | y 여기서 |는 비트 연산자 OR를 의미한다. 풀이 x + y와 x | y가 같다는 것은 2진수로 바꾸었을 때, 1의 위치가 서로 다르다는 것을 의미한다. 예를 들어 x가 5(101) y가 2(10)이라면 101 + 10 = 101 | 10 = 111로 같다. 이때 y를 구하는 것임으로 x를 기준으로 y를 설명하자면, x가 1이면 y는 0을 가지고 x가 0일 때 y는 1 혹은 0을 가질 수 있다는 것이다. k번 째 y는 1 혹은 0이 들어가는 자리를 조절하여 구할 수 있다. 첫 번째 y는 x가 0인 곳에 1(1)이 들어가면 되고 두 번째 y는 x가 0인 곳에 2(10)가 들어가면 된다. 위의 그림에서 검..

문제 n개의 1차원 숫자 배열이 주어졌을 때, 연속된 부분합이 m으로 나누어 떨어지는 경우의 수를 구하는 문제이다. 풀이 부분합을 m으로 나누었을 때 나누어 떨어지는지가 문제임으로 나머지끼리의 연산을 통해 문제를 풀 수 있다. 특히 1차원 부분합은 누적합의 뺄셈을 통해 구할 수 있음으로 $ partSum = prefixSum[j] - prefixSum[i]$ $( i < j ) $ 나머지가 같은 누적합의 뺄셈 계산을 통해 m으로 나눈 나머지가 0이 되는 부분합을 구할 수 있다. 부분합을 구할 때는 항상 뒤에 위치한 j번째 누적합에 i번째 누적합을 빼야한다. (i < j) 즉, 나머지의 수가 같은 누적합의 조합을 통해 나머지가 0이 되는 부분합의 경우의 수를 구할 수 있다. $_nC_2 = \frac{n ..