뚝딱뚝딱

https://www.acmicpc.net/problem/1149

💡 RGB거리

[문제]
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

[입력]
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

[출력]
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

✅ 문제 풀이

이 문제는 전형적인 DP 문제이다.

집은 R,G,B 세 색상 중 하나로 칠할 수 있는데, 인접한 집끼리는 색이 겹쳐서는 안된다.

그렇게 칠했을 때 모든 집을 칭하는 최소 비용을 구한다.

일단 입력으로 주어지는 각 집당 페인트 비용을 저장하기 위해서 2차원 배열을 사용해보자.

문제에서 주어진 예시를 사용할 것이다.

행은 집의 번호, 열은 각 집의 R,G,B 비용이다.

첫번째 집까지 칠했을 때는 첫번째 집에서 고른 비용이 저장되는 것이고, 두번째 집까지 칠했을 때는 첫번째 집까지 쓰인 비용+두번째 집에서 고른 비용으로 값이 정해진다. 따라서 다음과 같은 점화식을 따른다.

d[i]=d[i-1]+a[i]

그런데, 비용을 최소로 한다고 해서 모든 집에서 가장 작은 비용을 선택해버린다면, 위 예에 따르면 26, 49, 13이 가장 최소가 되어버리고, 모두 빨간색으로만 칠하게 되어버린다. 이는 조건을 위배하게 된다.

따라서 이전 집에서 어떤 색을 칠했는지에 따라서 이번 집에 칠할 수 있는 색이 2개로 추려져야 한다.

그러므로 이전 집을 R로 칠했을때, G로 칠했을때, B로 칠했을때를 모두 계산하고 나서, 최종 집까지 칠했을때 세 값중 최소값이 답이 될 수 있다.

이때 현재 집(i번 집)에 R을 칠하고자 한다면 이전집(i-1)이 G또는 B가 칠해졌어야 하고, 이 둘 중 최소 비용에 현재 집의 R 비용을 더한 값이 d[i][0]이 될 수 있다.

이를 점화식으로 나타내면 다음과 같다.

d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0]; 
d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];

점화식에 따르면 위 표와 같이 정리될 수 있고, 이는 i번째 집까지 칠했을 때의 비용을 나타낸다.

따라서 위 예시의 답은 3번째 집까지 칠했을 때의 비용 96,172,146 중에 최소값인 96이 되는 것이다.

min(min(d[t][0], d[t][1]), d[t][2])

이 식을 통해서 답을 구할 수 있다. (t는 마지막 집의 번호이다)

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	vector<vector<int>> d(t + 1, vector<int>(3, 0));
	vector<vector<int>> a(t + 1, vector<int>(3, 0));

	for (int i = 1; i <= t; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
		d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0];
		d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
		d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];
	}

	int answer = min(min(d[t][0], d[t][1]), d[t][2]);

	cout << answer;

	return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV13_BWKACUCFAYh&categoryId=AV13_BWKACUCFAYh&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

난이도⭐⭐⭐

✅ 문제 풀이

• 이 문제의 핵심은 굳이 100*100의 배열에 입력을 저장할 필요 없이, 입력을 받으면서 누적합을 구하고, max를 갱신해 나가면 된다는 것이다.
• 입력을 받을 때, 행을 기준으로 열들을 받는다. 따라서 2중 for문을 사용한다.
• 2중 for문에서 행이 먼저 돌기 때문에, 한 행의 값을 입력받을 때 100개의 열 값을 받는다.
• 따라서 row는 각 행마다 누적합을 구하고, 현재의 max와 비교해서 큰 값을 갱신한다.
• col은 각 행마다 한번에 100개씩 주어진다. 따라서 크기가 100인 배열을 선언해서, 해당 열에 누적하도록 하였다.
• 열의 최대값은 2중 for문이 끝난 후, 구해진 누적값들을 서로 비교해 최대를 가리고, 현재의 max와 비교해 갱신한다.
• 대각선은, 2중 for문에서 현재의 행과 열이 같은 값이면(if) 오른쪽방향 대각선의 누적합에, 행과 열을 더했을 때 99이면(else if) 왼쪽방향 대각선의 누적합에 더하도록 하였다. 마찬가지로 2중 for문이 끝난 후 두 값중 max를 구하고, 현재의 max와 비교해 갱신한다.
• 최종 max를 출력한다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 0; i < 10; i++) {
		int t;
		cin >> t;//test case number

		vector<int> col(100,0);
		int rcross = 0;
		int lcross = 0;

		int m = 0;

		for (int j = 0; j < 100; j++) {
			int row = 0;
			for (int k = 0; k < 100; k++) {
				int temp;
				cin >> temp;
				row += temp;
				col[k] += temp;
				if (j == k) rcross += temp;
				else if ((j + k) == 99) lcross += temp;
			}
			m = max(m, row);
		}
		
		for (int j = 0; j < 100; j++) {
			m = max(m, col[j]);
		}

		m = max(m, max(rcross, lcross));
		
		cout << "#" << t << " " << m << "\n";

	}
	return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV139KOaABgCFAYh&categoryId=AV139KOaABgCFAYh&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

✅ 문제 풀이

• 상자의 높이를 입력 받은 벡터에서, 가장 큰 값은 1 줄이고, 가장 작은 값은 1 늘리는 식으로 평탄화할 수 있다.
• 한번 덤프를 수행하고 날 때마다, 최소의 상자 높이와 최대의 상자 높이를 갖는 벡터의 위치가 달라진다.
• 이를 쉽게 찾기 위해서 매 덤프마다 벡터를 오름차순 정렬하고 시작하기로 했다.
• 그렇게 하면 벡터의 0번은 항상 가장 작고, 99번은 항상 가장 크기 때문이다.
• 따라서 정렬 후, 벡터의 99번째와 0번째의 차이가 1 또는 0이라면 더이상 상자를 옮기지 않아도 되기 때문에, break문으로 덤프를 멈추도록 한다. 그렇지 않다면, 평탄화가 이루어 져야 하므로 99번째 상자는 하나 줄이고, 0번째 상자는 하나 높여준다.
• 그럼 다음 덤프에서 다시 오름차순 정렬되고, 위의 과정을 반복하면 된다.
• 덤프를 모두 수행하고 나서는, 최종적으로 한번더 오름차순 정렬해준 뒤, 99번째에서 0번째 값을 뺀 값을 출력하도록 하면 된다.

=> 굉장히 naive한 방법이지만, c++ 기준 시간은 10초까지 인정되므로 pass되는 코드이다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 1; i <= 10; i++) {
		int n;
		cin >> n;
		vector<int> arr(100);
		for (int j = 0; j < 100; j++) {
			cin >> arr[j];
		}
		
		int answer;
		for (int j = 0; j < n; j++) {
			sort(arr.begin(), arr.end());
			if (((arr[99] - arr[0]) == 1) || ((arr[99] - arr[0]) == 0)) {
				break;
			}
			else {
				arr[99]--;
				arr[0]++;
			}
		}
		sort(arr.begin(), arr.end());
		answer = arr[99] - arr[0];
		cout << "#" << i << " " << answer << "\n";
	}
	return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

난이도 D3 ⭐⭐⭐

✅ 문제 풀이

• 처음 두 건물과, 마지막 두 건물은 항상 높이가 0이다.
• 따라서 세번째 건물부터 기준으로하여, 앞에 두 건물과 뒤에 두 건물 보다 큰지 확인한다.
• 앞 뒤로 총 4개의 건물보다 크다면, 기준이 되는 현재 건물의 높이에서 4개 건물 중 가장 큰 건물의 높이를 뺀 값이 뷰를 확보할 수 있는 세대 수가 된다.
• 이를 모든 건물에 대해서 반복하며 세대 수를 누적해가면, 각 테스트케이스의 답이 된다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("input.txt", "r", stdin);
    for (int i = 1; i <= 10; i++) {
        int n;
        cin >> n;
        vector<int> arr;
        for (int j = 0; j < n; j++) {
            int temp;
            cin >> temp;
            arr.push_back(temp);
        }
 
        int count = 0;
        for (int j = 2; j < n-2; j++) {
            int cent = arr[j];
            if (arr[j - 2] < cent && arr[j - 1] < cent && arr[j + 1] < cent && arr[j + 2] < cent) {
                int m1 = max(arr[j - 2], arr[j - 1]);
                int m2 = max(arr[j + 1], arr[j + 2]);
                count += cent - (max(m1, m2));
            }
        }
 
        cout << "#" << i << " " << count << "\n";
    }
    return 0;
}

https://www.acmicpc.net/problem/1764

💡 듣보잡

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

[입력]
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

[출력]
듣보잡의 수와 그 명단을 사전순으로 출력한다.

✅ 문제 풀이

• set 자료구조에 입력받은 이름들을 저장할건데, 듣도 못한 사람들을 입력받고 저장해둔다.
• 그리고 보도 못한 사람들을 입력받을 때마다, set의 find함수를 사용해서, 보도 못한 사람이 있는지 확인하고, 있으면 vector에 저장한다.
• 마지막에 vector의 크기를 출력하고, 사람을 사전 순으로 출력해야 하므로 sort함수를 통해 오름차순 정렬한다.
• 그리고 정렬된 vector의 내용을 모두 출력한다.

✏ 코드 전문

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	set<string> arr;
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		arr.insert(str);
	}

	vector<string> answer;

	for (int i = 0; i < m; i++) {
		string str;
		cin >> str;
		
		auto it = arr.find(str);
		if (it != arr.end()) answer.push_back(str);
	}

	cout << answer.size() << "\n";
	
	sort(answer.begin(), answer.end());

	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << "\n";
	}

	return 0;
}

https://www.acmicpc.net/problem/2667

💡 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

[입력]
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

[출력]
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

✅ 문제 풀이

• 주어진 배열에서 연속적인 1을 하나의 영역으로 보고, 그 영역의 크기와, 총 영역의 개수를 구하는 문제이다.
• 2중 for문으로 순회하며 각 칸이 1인지 확인한다.
• 1인 경우에는 count를 0으로 초기화하고, dfs를 호출한다.
• dfs에는 현재 칸의 좌표값과, count, 그리고 2차원 배열의 정보를 인자로 넘겨준다.

• dfs의 동작은 다음과 같다.
• dfs가 호출되면, 현재 칸을 방문했으므로 배열의 값을 0으로 갱신해준다.
• 그리고 해당 영역에 대한 크기를 구하기 위해서 count를 1 증가 시켜준다.
• 현재 칸을 기준으로 동서남북 방향에 대해서 총 4번 탐색할 건데, 동서남북이 배열의 인덱스에 유효한지 확인하고, 그 배열 값이 1이라면 dfs를 재귀 호출하여 이어 탐색하도록 한다.

• 이렇게 되면, 한 영역을 처음 방문하고 나서는 동일한 영역에 대해서는 재귀호출 시 다 처리 되기 때문에, main함수의 2중 for문 순회시에는 딱 각 영역의 시작만으로 구분할 수 있다. 따라서 main의 2중 for문 순회에서 배열 값이 1인 경우에는 dfs를 호출한 뒤, 영역의 개수를 하나 증가시키고, dfs 결과 계산된 해당 영역의 크기인 count를 영역의 크기만 저장하는 배열 cnt에 넣어둔다.
• 2중 for문을 모두 순회하고 나면 sum에는 영역의 개수가 저장되는 것이고, cnt에는 각 영역의 크기가 저장되어 있을 것이다.
• 문제에서 출력 시 영역의 크기는 오름차순으로 출력하도록 하라고 되어있으므로, sort함수를 사용하여 cnt 벡터를 오름차순 정렬 시켜주었다.
• 그리고 sum과 cnt를 모두 출력해준다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int n;

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void dfs(int x, int y, int &count, vector<vector<int>> &arr) {
	arr[x][y] = 0;
	count++;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < n&&ny >= 0 && ny < n&&arr[nx][ny] == 1) {
			dfs(nx, ny, count, arr);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	vector<vector<int>> arr(n, vector<int>(n));

	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < n; j++) {
			arr[i][j] = str[j]-'0';
		}
	}

	vector<int> cnt;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 1) {
				int count = 0;
				dfs(i, j, count, arr);
				sum++;
				cnt.push_back(count);
			}
		}
	}

	sort(cnt.begin(), cnt.end());

	cout << sum<<"\n";
	for (int i = 0; i < cnt.size(); i++) {
		cout << cnt[i] << "\n";
	}

	return 0;
}