오늘은 백준 2775번 부녀회장이 될테야 풀이를 할 예정이다. 그간 이런저런 일이 많아서 블로그에 소홀했는데,, 여튼! 시작해보자
바로 본론으로 들어가서,,
a층 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들 수의 합만큼 사람들을 데려와 살야아 한다. 이 때, 0층 N호에는 총 N명이 산다.
→ 0층 1호에는 1명, 2호에는 2명, ..., 14호에는 14명 이 산다.
→ 1층 3호에 살려면 6명, 2층 3호에 살려면 10명을 데려와 살아야 한다.
문제에 따르면 1층 3호에 살려면 6명은 다음과 같이 구해진다
(1-1)층 1호~3호까지 사람의 수의 합 = 0층 1호 + 0층 2호 + 0층 3호 = 1 + 2 + 3 = 6명 이다.
마찬가지로, 2층 3호의 사람을 구해보면 (2-1층) 1호~3호까지 사람 수의 합 = 1층 1호 + 1층 2호 + 1층 3호 = 1 + 3 + 6 = 10명
잘 보면, subtree가 반복되는걸 확인할 수 있다. 만약 3층 4호, 5층 6호 ... 로 확장해 나갈수록, k-1, k-2, k-3, ... (k-m >= 0)이 반복되고 이에 대응하는 n호에 대한 사람 수도 subtree에서 반복되어 나타날 것이다. (만약 머리에 안그려진다면, 직접 그려서 확인하는걸 추천한다.)
subtree가 반복될 때 우리는 Dynamic Programming을 통해 쉽게 해당 문제를 풀 수 있다. 층에 대한 사람 수를 결정해 놓고, 해당 호수를 출력하면 문제 풀이는 끝이난다.
→0층 1호에는 1명, 2호에는 2명, ..., 14호에는 14명 이 산다.
위 조건에 맞게, 1호~14호 까지는 1~14의 값을 넣어주고, 이후 층 부터 (k-1)층 n호에 대한 사람 수를 불러와 더해주면 된다.
문제 풀이를 위해 1차원 배열을 선언하고, 14개씩 끊어서 하나의 층을 표현할 예정이다.
for(int i = 14; i < rooms.length; i++){
int floor = i / 14;
int number = (i % 14) + 1;
int underFloor = floor-1;
int underValue = 0;
for(int j = 0; j < number; j++){
underValue += rooms[underFloor * 14 + j];
}
rooms[i] = underValue;
}
따라서 위의 표정을 보면, 층수는 ( i / 14 )의 값을 갖게 되고, 호수(number)는 ( i % 14 ) +1이 된다. 1을 더해준 이유는, 실제 호수는 0~13이 아닌 1~14호기 때문이다.
이후 아래층의 1호~number호 까지의 방에 살고있는 사람수 (underValue)를 계산한다. 이 때, underFloor*14인 경우는 1차원 배열로 선언했기 때문에, 바로 아래층의 위치를 구하기 위해 14를 곱해줘야 하기 때문이다.
최종 코드
public class Number2775 {
public static void main(String[] args) throws IOException {
int[] rooms = new int[15*14];
for(int i = 0; i < 14; i++){
rooms[i] = i+1;
}
for(int i = 14; i < rooms.length; i++){
int floor = i / 14;
int number = (i % 14) + 1;
int underFloor = floor-1;
int underValue = 0;
for(int j = 0; j < number; j++){
underValue += rooms[underFloor * 14 + j];
}
rooms[i] = underValue;
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while(T-- > 0){
int k = Integer.parseInt(br.readLine());
int n = Integer.parseInt(br.readLine());
System.out.println(rooms[k * 14 + (n-1)]);
}
}
}rooms의 배열이 14 * 14가 아닌 이유는, 아파트의 층수가 0층~14층까지 존재하기 때문에 총 15개의 층에 대해 연산해야 하기 때문이다.
결과는.. 정답!
'공부 > 알고리즘' 카테고리의 다른 글
| [알고리즘] BackTracking 기법, N Queen 예시/ 퇴각검색 기법 (0) | 2021.08.26 |
|---|---|
| [알고리즘] 동적 계획법 / Dynamic Programming (0) | 2021.08.23 |
| [Java 코딩테스트] 백준 2292번 문제 풀이 / 백준 벌집 문제 (0) | 2021.08.10 |
| [Java 코딩테스트] 백준 3052 문제풀이 / 배열 나머지 수 구하기 (0) | 2021.07.25 |
| [Java 코딩테스트] 백준 10818 문제풀이 / 배열 없이 최소 최대 구하기 (0) | 2021.07.22 |
