#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
int cnt = 0; // 현 시점에 있는 쇠막대기
int stickNum = 0; // 현재까지 잘린 막대기 조각 개수
cin >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
if (i < s.size() - 1 && s[i + 1] == ')') { // 레이저일때 -> 상황 A
stickNum += cnt;
i++; // 레이저이므로 다음 s[i]는 ')'이므로 다음 문자는 뛰어넘음
}
else { // 여는 괄호일 때 -> 상황 B
cnt++;
}
}
else { // 닫는 괄호일 때 -> 상황 C
cnt--;
stickNum++;
}
}
cout << stickNum;
return 0;
}
일단 문자열로 받은 다음 문자열의 길이만큼 for문을 돌면서 순차적으로 그 시점에 있는 쇠막대기의 개수와 그 시점에서 현재까지 잘린 막대기 조각의 개수를 세었다.
가중치가 없는 최단경로를 구하는 것이기 때문에 BFS로 풀었다. 한 가지 주의할 점은 큐에서 빼낼 때 한 번에 하나씩 빼내는 것이 아니라 같은 시점에 큐에 넣어진 것들은 한번에 큐에서 빼주는 것이다. 그래야 물이 차는 속도와 맞출 수 있다. 나는 원래 절대 구글링을 하거나 힌트도 보지 않고 풀지만 이 문제는 조금 어려운 것 같아서 푸는 방법을 혼자 생각해 낸 것이 특히 더 뿌듯했다. 물이 차는 것은 딱히 BFS나 DFS로 풀지 않고 그냥 매 시점 물이 찬 곳과 인접한 동서남북을 물로 채워주었다. 다음에 찰 예정인 곳은 콤마(,)로 표시해놓고 고슴도치가 이동한 후에 별(*)로 표시해주었다.
4ms로 통과했다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <tuple>
#include <queue>
using namespace std;
int dr[] = { 0, 0, -1, 1 };
int dc[] = { 1, -1, 0, 0 };
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
pair<int, int> waterLocation;
pair<int, int> sLocation;
vector<vector<char>> v(n, vector<char>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> v[i][j];
if (v[i][j] == '*')
waterLocation = make_pair(i, j);
if (v[i][j] == 'S')
sLocation = make_pair(i, j);
}
}
int minLength = -1;
queue<tuple<int, int, int, int>> q;
q.push(make_tuple(sLocation.first, sLocation.second, 0, 0));
vector<vector<bool>> visited(n, vector<bool>(m, false));
int cnt = 1;
bool arrivedFlag = false;
while (!q.empty()) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (v[i][j] == '*') {
for (int k = 0; k < 4; k++) {
int row = i + dr[k];
int col = j + dc[k];
if (row >= n || col >= m || row < 0 || col < 0 || v[row][col] != '.')
continue;
v[row][col] = ',';
}
}
}
}
while (!q.empty()) {
tuple<int, int, int, int> cur = q.front();
if (get<3>(cur) != cnt - 1)
break;
q.pop();
if (v[get<0>(cur)][get<1>(cur)] == 'D') {
minLength = get<2>(cur);
break;
}
if (!visited[get<0>(cur)][get<1>(cur)]) {
visited[get<0>(cur)][get<1>(cur)] = true;
for (int i = 0; i < 4; i++) {
int row = get<0>(cur) + dr[i];
int col = get<1>(cur) + dc[i];
if (row >= n || col >= m || row < 0 || col < 0 || !(v[row][col] == '.' || v[row][col] == 'D'))
continue;
if (v[row][col] == 'D') {
arrivedFlag = true;
minLength = get<2>(cur) + 1;
break;
}
q.push(make_tuple(row, col, get<2>(cur) + 1, cnt));
}
}
if (arrivedFlag)
break;
}
if (arrivedFlag)
break;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (v[i][j] == ',') {
v[i][j] = '*';
}
}
}
cnt++;
}
if (minLength == -1)
cout << "KAKTUS";
else
cout << minLength;
return 0;
}
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <set>
using namespace std;
int n;
vector<int> v;
set<int> answer;
int number;
void permutation(int num, vector<int> result) {
if (num == n) {
bool isAllPrime = true;
for (int i = 0; i < n; i++) {
number = 0;
for (int j = 0; j <= i; j++) {
number += (result[j] * pow(10, i - j));
}
if (number == 1)
isAllPrime = false;
for (int j = 2; j <= sqrt(number); j++) {
if (number % j == 0) {
isAllPrime = false;
break;
}
}
}
if (isAllPrime) {
number = 0;
for (int i = 0; i < n; i++) {
number += (result[i] * pow(10, n - 1 - i));
}
answer.insert(number);
}
return;
}
for (int i = 1; i <= 9; i++) {
result[num] = i;
permutation(num + 1, result);
}
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n;
v = vector<int>(n);
permutation(0, vector<int>(n));
for (set<int>::iterator iter = answer.begin(); iter != answer.end(); iter++) {
cout << *iter << '\n';
}
return 0;
}
이거였다. 그런데 이것의 문제는 일단 모든 가능한 n자리 수를 다 구하고 그 다음에 그것이 신기한 소수인지 확인했다.
그리고 신기한 소수인지 확인할 때도 예를 들어 n이 4일 때 6666이라는 절대 신기한 소수가 될 수 없는 수라도 8가 소수인지 확인, 88아 소수인지 확인, 889이 소수인지 확인, 8888이 소수인지 확인을 해주었다. 너무나도 비효율적이라는 것을 깨달았다. 애초에 8이 소수가 아닐 때부터 얘는 신기한 소수의 대상에서 제외를 해줘야 하는데 말이다.
그래서 두번째 코드는 이렇게 수정하였다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <set>
using namespace std;
int n;
vector<int> v;
set<int> answer;
int number;
void permutation(int num, vector<int> result) {
if (num == n) {
bool isAllPrime = true;
for (int i = 0; i < n; i++) {
if (!isAllPrime)
break;
number = 0;
for (int j = 0; j <= i; j++) {
number += (result[j] * pow(10, i - j));
}
if (number == 1)
isAllPrime = false;
for (int j = 2; j <= sqrt(number); j++) {
if (number % j == 0) {
isAllPrime = false;
break;
}
}
}
if (isAllPrime) {
number = 0;
for (int i = 0; i < n; i++) {
number += (result[i] * pow(10, n - 1 - i));
}
answer.insert(number);
}
return;
}
for (int i = 1; i <= 9; i++) {
result[num] = i;
permutation(num + 1, result);
}
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n;
v = vector<int>(n);
permutation(0, vector<int>(n));
for (set<int>::iterator iter = answer.begin(); iter != answer.end(); iter++) {
cout << *iter << '\n';
}
return 0;
}
일단 모든 가능한 n자리의 수를 다 구하는 것까지는 똑같았고 n이 4일 때 8888이면 처음 8을 확인해보고 소수가 아니면 그냥 for문을 더 이상 돌지 않고 끝내었다. 하지만 이것도 시간초과가 났다.
그래서 세 번째에는 애초에 신기한 소수가 될 수 없다면 재귀함수를 호출하지 않고 가지를 쳐버렸다.
이게 바로 백트래킹인데 나는 바보짓을 했다는 것을 스스로 알아내었다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <set>
using namespace std;
int n;
vector<int> v;
set<int> answer;
int number;
bool flag;
void permutation(int num, vector<int> result) {
if (num == n) {
number = 0;
flag = true;
for (int i = 0; i < n; i++) {
number += (result[i] * pow(10, n - 1 - i));
}
answer.insert(number);
return;
}
for (int i = 1; i <= 9; i++) {
result[num] = i;
number = 0;
flag = true;
for (int j = 0; j <= num; j++) {
number += (result[j] * pow(10, num - j));
}
if (number == 1)
flag = false;
for (int j = 2; j <= sqrt(number); j++) {
if (number % j == 0) {
flag = false;
break;
}
}
if(flag)
permutation(num + 1, result);
}
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n;
v = vector<int>(n);
permutation(0, vector<int>(n));
for (set<int>::iterator iter = answer.begin(); iter != answer.end(); iter++) {
cout << *iter << '\n';
}
return 0;
}
