[백준 7348] 테이블 옮기기 (C++)

문제 링크: https://www.acmicpc.net/problem/7348

7348번: 테이블 옮기기

1. 주의할 점

- 처음에 입력받는 숫자가 두번째 숫자보다 클 수도 있다

- 서로 마주보는 숫자는 공통된 통로를 지닌다

 

2. 구현

- 1-2, 3-4, 5-6,...,399-400이 같은 복도를 지닌다 -> 모두 1씩 빼고 2로 나눴을때 같은 몫을 가진다

- 출발 방과 도착 방번호를 입력받은 후, 출발 방이 작은 숫자가 되도록 바꾼다

- [(출발 방-1)/2,(도착 방-1)/2] 까지 DP배열의 값을 1씩 증가시킨다

- DP배열에서 가장 큰값 *10을 출력한다

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[200];
int main() {
	int test, num, start, destination;
	cin >> test;
	for (int t = 0; t < test; t++) {
		for (int i = 0; i < 200; i++)
			dp[i] = 0;
		cin >> num;
		for (int k = 0; k < num; k++) {
			cin >> start >> destination;
			int temp;
			if (start > destination) {
				temp = destination;
				destination = start;
				start = temp;
			}
			start = (start - 1) / 2;
			destination = (destination - 1) / 2;
			for (int i = start; i <= destination; i++)
				dp[i] += 10;
		}
		int result = 0;
		for (int i = 0; i < 200; i++)
			result = max(result, dp[i]);
		cout << result << '\n';
	}
	system("pause");
	return 0;
}