0과 1의 쉼터

문제https://www.acmicpc.net/problem/28288풀이가로, 세로가 5 * N으로 이루어진 일정을 참고해, 각 열에 존재하는 'Y'의 비율 가장 많은 요일을 출력하는 문제다.만약, 각 일정이 가지는 Y의 수가 동일한 경우 ','를 구분자로 같이 출력해주면 된다.우선, 문자열 결합을 쉽게 하기 위해 StringJoiner를 사용했다.이후 입력받은 char 배열에 대해 각 열에 존재하는 Y의 개수를 cnt 배열에 기록해주자.동시에 최대 개수를 따로 기록해주자.이제 cnt 배열에서 기록한 최대 개수와 동일한 개수의 Y가 존재하는 일정을 구분자와 결합해 출력하면 된다.소스코드보기

문제은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 S1,S2,⋯,S, S_2, S_N번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a$a$개, 뒤에서 b$b$개의 과일을 빼면 Sa+1,Sa+2,⋯,SN−b−1,SN−b번 과일, 총 N−(a+b)$N-(a+b)$개가 꽂혀있는 탕후루가 됩니다. (0≤a,b; a+b이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가..

문제 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱걸이를 5회 하는 기적의 운동 루틴을 통해 뇌와 근육을 동시에 단련한다. 근육을 단련할 때 식단이 정말로 중요하다는 것을 아는 인범이는 탄수화물이 많은 밥이나 빵 따위의 아침 식사를 대신해 단백질이 많은 계란찜을 해먹는다. 계란찜을 먹기 위해서는 계란을 깨야 하는데, 인범이는 힘이 너무 넘치는 나머지 부엌의 대리석을 이용해 계란을 깨면 늘 껍데기가 산산조각나 뒷처리가 너무 어렵게 되곤 한다. 어떻게 하면 계란을 조심스럽게 깰 수 있을까 고민하던 인범이에게 유현이는 굉장히 좋은 해결책을 알려주었다. 바로 계..

문제 algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 algospot.com 풀이 버튼을 누르는 순서는 중요하지 않지만, 4번 누르면 시계가 원래대로 돌아오기 때문에 O(4^10)인 완전 탐색이 가능하다. 우선 버튼을 눌렀을 때 시간이 변하는 시계들을 다음과 같이 정리해주자. 각 배열의 첫번째 요소는 배열의 길이를 의미한다. 버튼을 누르는 횟수는 4회 미만이므로 버튼을 눌렀을 때 시계를 바로 업데이트 하는 것이 아닌 다음 버튼을 누르는 Recursive Call을 해서 분기를 ..

문제 algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 algospot.com 풀이 주어지는 보드의 빈 공간에 3칸으로 만들어진 'ㄴ' 모양의 블럭으로 전부 다 덮는 경우의 수를 구하는 문제다. 한 위치에서 12개의 경우의 수가 주어지지만, 블럭을 순차적으로 놓기 때문에 한 방향에 대해서만 생각해도 충분하다. 위/왼쪽을 기준으로 채운다고 가정했을 때 필요한 블럭은 아래와 같다. 여러번 사용해야하므로 미리 만들어두자. 가장 왼쪽 위 부터 비어있는 공간을 찾으며 dfs를 진행하자. 블럭을 다 채웠다면 못찾고 종료하므..

문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 N개의 정수에 대한 조합 가능한 모든 부분 수열을 찾고, 부분 수열의 합이 S와 일치하는 경우를 찾아야 한다. 크기가 양수인 부분 수열에 대한 합비교 이므로 S가 0일 때 부분 수열의 길이가 0인 경우는 제외해야 한다. combinations 사용 버전 N개의 정수로 이루어진 수열에 대해 1 ~ N개로 생성할 수 있는 조합을 전부 생성해 합을 비교하는 방법이다. 가장 짧고 간결한 방법이다. 부분 수열의 합이 S와 일..

문제 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 N / 2명씩 두 팀을 이룰 때, 각 팀에 속하는 팀원들의 번호로 만들 수 있는 조합에 따른 능력치 합을 구해야 한다. 이때, 두 팀의 능력치 합에 대해 최대한 차이가 없도록 팀원을 정해야 한다. 만약 N명이 한 팀이라면, S[0][0] ~ S[N-1][N-1]이 그 팀의 능력치가 된다. 이 팀에서 2/N명을 제외시켜 새로운 팀을 만든다면, 새로운 팀의 팀원 번호와 조합 가능한 모든 S를 제외시키면 두 팀의 능력치의 합을 구할 수 있다. 따라서 각 팀의 번호와 조합 가능한 ..

문제 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 풀이 문제에서 주어진 5번 조건에 따라 기둥과 기둥사이에는 오목하게 들어간 부분 없이 가장 작은 창고 다각형의 면적을 구해야 한다. 때문에 이 문제는 가장 큰 높이의 기둥의 위치( divL ) 중심으로 문제를 분할할 수 있다. 기둥의 순서가 무작위지만, L의 최대가 1000이므로 선형 계산은 오래 걸리지 않는다. 입력받은 기둥들에 대한 정보를 배열에 기록해주면서 divL을 구하자. 이제 왼쪽 끝 기둥부터 divL까지, 오른쪽 끝 기둥에서 d..