처음에는 combination으로 모든 조합을 다 구해봤다. 당연히 시간초과가 났다. N이 100 이하니까 당연한 결과였다.
그래서 다시 생각한 방법이 일단 map을 만들었다. key 값을 1~N까지로 하고 둘째 줄에 들어있는 값들을 value로 해서 넣었다.
그 다음에 i = 1부터 시작해서 i = N까지 반복을 하였다. 예를 들어 i = 1이라면 map[1]에 있는 value를 key에 대입하여 이제 map[1]이 key가 된다. 그 다음에 또 그 key를 가지고 map[key]로 간다. 그 다음에도 또 반복을 하는 것이다. 그런데 이미 방문했던 곳이라면 사이클이 생겼거나 숫자가 중복된다는 것이다. 숫자가 중복됐다는 것은 잘못된 것이다. 왜냐하면 첫번째 줄은 1부터 N이므로 숫자가 중복될 수가 없다. 사이클이 생긴 곳은 visited에 방문했다고 표시한다. 이런 식으로 사이클이 생긴 것들끼리 합치면 정답이 된다. 예를 들어 i = 5일 때 map[5]에 들어있는 숫자가 5라도 이것은 사이클이 발생한 것이다.
주어진 정수들이 3, 1, 1, 5, 5, 4, 6일 때 tempVisited와 map은 다음과 같다.
이런 식으로 i=7까지 반복하면 된다.
visited가 true인 것들이 정답이다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
map<int, int> m;
int temp;
for (int i = 1; i <= n; i++) {
cin >> temp;
m[i] = temp;
}
vector<int> answer;
vector<int> real;
vector<bool> visited(n + 1, false);
for (int i = 1; i <= n; i++) {
vector<bool> tempVisited(n + 1, false);
int key = i;
answer.clear();
if (!visited[i]) {
while (true) {
tempVisited[key] = true;
key = m[key];
answer.push_back(key);
if (tempVisited[key]) {
if (key != i) {
answer.clear();
}
break;
}
}
}
for (int i = 0; i < answer.size(); i++) {
int index = answer[i];
visited[index] = true;
}
}
for (int i = 1; i <= n; i++) {
if (visited[i]) {
real.push_back(i);
}
}
sort(real.begin(), real.end());
cout << real.size() << '\n';
for (int i = 0; i < real.size(); i++) {
cout << real[i] << '\n';
}
return 0;
}
for문 안에서의 방문했는지 아닌지는 tempVisited에 저장했고 전체에서 방문했는지 아닌지 즉 정답을 체크하는 것은 visited에 저장했다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int main() {
cin.tie(NULL);
int n, w, l;
cin >> n >> w >> l;
vector<int> v(n);
queue<int> q;
vector<int> count;
for (int i = 0; i < n; i++) {
cin >> v[i];
}
q.push(v[0]);
count.push_back(w);
int index = 1;
int time = 1;
int totalWeight = v[0];
int weight;
while (!q.empty()) {
for (int i = 0; i < count.size(); i++) {
count[i]--;
}
if (count[0] == 0) {
weight = q.front();
q.pop();
totalWeight -= weight;
count.erase(count.begin());
}
if (index < n && totalWeight + v[index] <= l) {
q.push(v[index]);
count.push_back(w);
totalWeight += v[index];
index++;
}
time++;
}
cout << time;
return 0;
}
q라는 이름으로 큐를 하나 만들어놓고 다리에 진입한 트럭들은 큐에 집어넣었다. 그리고 큐에 들어간 트럭들의 무게들은 totalWeight에 더해주었다. 트럭이 다리에서 벗어나면 즉, 큐에서 빠지게 되면 totalWeight에서도 트럭의 무게만큼 빼주었다.
그리고 트럭이 단위시간에 단위길이만큼만 이동하기 때문에 다리에 진입한 트럭 하나마다 얼마나 더 가야하는지 남은 길이(남은 시간)를 count라는 벡터에 저장해주었다. 당연히 처음에는 다리의 길이이고 단위시간이 지날 때마다 count[i]--로 1씩 빼주었다. count[i]가 0이 되는 순간 큐에서 트럭을 빼고 count[i]도 벡터에서 제거해주었다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<vector<int>> v(n, vector<int>(m));
int length = min(n, m) - 1;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
for (int j = 0; j < m; j++) {
v[i][j] = stoi(s.substr(j, 1));
}
}
bool flag = false;
while (true) {
for (int row = 0; row + length < n; row++) {
for (int col = 0; col + length < m; col++) {
if (v[row][col] == v[row + length][col] && v[row][col] == v[row][col + length] && v[row][col] == v[row + length][col + length]) {
flag = true;
break;
}
}
if (flag)
break;
}
if (flag) break;
length--;
}
cout << (length + 1) *(length + 1);
return 0;
}
네모칸을 점점 줄여가면서 이동시키면서 네 꼭짓점의 값이 같은 정사각형을 발견해나가면 된다.
변의 길이는 가로, 세로의 길이 중 짧은 것으로 시작한다. (그것을 length로 뒀다)
기준이 되는 점인 (row, col)을 왼쪽에서 오른쪽으로, 위에서 아래로 옮겨가면서 네 칸의 값이 같을 때까지 반복한다.
끝까지 갔는데 발견되지 않으면 length를 줄이고 그것을 반복한다.
주의할 점은 변의 길이가 3이면 세 칸을 차지하는 것이니까 0~3이 아니라 0~2라는 것이다. 따라서 변의 길이가 3이면 length를 2가 되게 했다. row + length 했을 때 두 칸을 더해야 되니까. 그리고나서 나중에 크기를 구할 때에는 length에 1을 더해주었다.
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
int row = arr1.size();
int col = arr2[0].size();
int t = arr1[0].size();
int n;
vector<vector<int>> answer(row, vector<int>(col));
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
n = 0;
for (int k = 0; k < t; k++) {
n += (arr1[i][k] * arr2[k][j]);
}
answer[i][j] = n;
}
}
return answer;
}
행렬의 곱셈을 그대로 구현하면 된다. 3중 for문이라서 약간 헷갈렸지만 공책에 표시하면서 풀었더니 금방 쉽게 풀 수 있었다.
