어흥
[백준 15886] 내 선물을 받아줘 2 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/15886
1. 주의할 점
- 메모아이징을 사용한 DFS를 이용한다 (DP문제)
2. 구현
- Check[] 배열을 전부 -1로 초기화 한다
- 0~Num-1 까지 For문을 돌며 Check값이 -1이라면(아직 방문한 적이 없다면) DFS(int Idx, int Cnt)를 수행한다
- DFS(int Idx, int Cnt)는 Int형 함수로 return 값이 필요하다
- 우선 Check[Idx]값이 -1이 아니라면 Check[Idx] 값을 반환한다
- -1이라면 Check값을 Cnt로 설정하여 -1과는 차별화게 되게 현재 방문하고 있다는 표시를 남긴다
- 가장 왼쪽 칸이 W인 경우와 가장 오른쪽 칸이 E인 경우는 따로 예외처리를 한다
- Temp변수에 다음 이동해야 하는 칸에 대한 Return값을 돌려받고, Check[Idx] 값을 다시 Temp로 갱신한다
- For문이 종료 된후, 사용된 숫자가 몇 개인지 확인하고 출력한다
#include <iostream>
#include <algorithm>
using namespace std;
char arr[1000];
int check[1000], num, result = 0;
bool number[1001] = { false, };
int dfs(int idx, int cnt) {
if (check[idx] != -1) return check[idx];
int temp = check[idx];
check[idx] = cnt;
if (arr[idx] == 'E') {
if (idx + 1 == num) return cnt;
else
temp = dfs(idx + 1, cnt);
}
else if (arr[idx] == 'W') {
if (idx == 0) return cnt;
else
temp = dfs(idx - 1, cnt);
}
check[idx] = temp;
return temp;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> num;
int vv = 0;
for (int i = 0; i < num; i++)
cin >> arr[i];
for (int i = 0; i < num; i++)
check[i] = -1;
for (int i = 0; i < num; i++)
if (check[i] == -1)
dfs(i, ++vv);
for (int i = 0; i < num; i++) {
if (!number[check[i]]) {
number[check[i]] = true;
result++;
}
}
cout << result;
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 13977] 이항 계수와 쿼리 (C++) (0) | 2020.05.03 |
---|---|
[백준 1516] 게임 개발 (C++) (0) | 2020.05.03 |
[백준 11657] 타임머신 (C++) (0) | 2020.05.03 |
[백준 2887] 행성 터널 (C++) (0) | 2020.05.02 |
[백준 3860] 할로윈 묘지 (C++) (0) | 2020.05.01 |
Comments