전형적인 DP문제. 처음에는 근우의 입장에서만 생각하고 코드를 짠 후 당당하게 제출했는데 역시 당당하게 틀렸다. 해당 문제는 다음과 같이 근우의 차례일 때와 명우의 순서일 때를 나누어서 생각해야 한다.
(1) 근우의 순서일 때
- 왼쪽 카드를 선택하고 나머지 카드들에서 얻는 점수, 오른쪽 카드를 선택하고 나머지 카드들에서 얻는 점수 중 최댓값
(2) 명우의 순서일 때
- 왼쪽 카드 제외한 나머지 카드들에서 얻는 점수, 오른쪽 카드 제외한 나머지 카드들에서 얻는 점수 중 최솟값
- 근우가 점수를 작게 가져가게끔 만들어야하도록 최솟값일 때의 경우를 선택
간단한 코드이므로 코드 블락 단위의 설명은 주석으로 대체하겠음.
3. 전체 코드
defpickCard(turn, i, j):if i > j: return0if dp[i][j]: return dp[i][j] #이미 계산된 적이 있으면 해당 값 리턴#근우 차례if turn:
# i카드 + (i+1~j)범위 카드의 명우 순서 or j카드 + (i~j-1)범위 카드의 명우 순서 중 최대 스코어
score = max(pickCard(False, i+1, j) + cards[i], pickCard(False, i, j-1) + cards[j])
dp[i][j] = score
return score
#명우 차례elifnot turn:
# (i+1~j)범위 카드의 근우 순서 or (i~j-1)범위 카드의 근우 순서 중 최소 스코어# 각각 명우가 i, j 카드를 가져갔다고 가정하지만, 근우 입장의 점수를 계산하는 거기 때문에 카드 점수를 더해주지 않음
score = min(pickCard(True, i+1, j), pickCard(True, i, j-1))
dp[i][j] = score
return score
import sys
T = int(input()) #테스트케이스for _ inrange(T):
N = int(input()) #카드 개수
cards = list(map(int, sys.stdin.readline().split()))
dp = [[0for _ inrange(N)] for _ inrange(N)] #DP 배열 초기화
pickCard(True, 0, N-1) #카드가 (0~N-1)범위만큼 있고, 근우 순서일 때 얻는 점수 계산print(dp[0][N-1])
단순히 그래프의 순환을 찾아서 출력하는 문제. 순환을 찾기 -> 해당 순환의 첫노드와 마지막 노드까지를 answer 배열에 넣기 -> 다음 순환 찾기의 반복으로 풀 수 있었다.
(1) 순환 찾기
for (int i = 1; i <= N; i++) {
if (!visited[i] && !visited[nums[i]]) checkCycle(i); //현재 노드와 연결된 노드 둘 다 아직 방문한 적이 없는 노드라면 checkCycle
visited[i] = true; //visited 갱신
}
현재 노드와 연결된 노드를 둘 다 보는 이유는 현재 노드는 당연히 방문한 적이 없어야 하고, 연결된 노드가 이미 방문된 노드라면 앞에서 순환 검사를 이미 끝마쳤다는 소리이기 때문
voidcheckCycle(int node){
visited[node] = true; //visited 갱신int next = nums[node];
//만일 순환이 발생한다면if (visited[next]) {
addAnswer(next, node);//순환의 처음과 끝을 가지고 addAnswer수행return;
}
checkCycle(next); //순환이 발생하지 않으면 연결된 다음 노드로 이동
}
(2) answer배열에 추가하기
voidaddAnswer(int start, int goal){
int current = start;
answer.push_back(current);
// 그래프를 타고 다음 노드로 넘어가며 goal과 같은 노드에 다다르기 전까지 answer 배열에 추가while (current != goal) {
current = nums[current];
answer.push_back(current);
}
}
3. 전체 코드
#include<iostream>#include<algorithm>#include<vector>usingnamespace std;
int N;
int nums[101];
bool visited[101];
vector<int> answer;
voidaddAnswer(int start, int goal){
int current = start;
answer.push_back(current);
while (current != goal) {
current = nums[current];
answer.push_back(current);
}
}
voidcheckCycle(int node){
visited[node] = true;
int next = nums[node];
if (visited[next]) {
addAnswer(next, node);
return;
}
checkCycle(next);
}
intmain(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++) cin >> nums[i];
for (int i = 1; i <= N; i++) {
if (!visited[i] && !visited[nums[i]]) checkCycle(i);
visited[i] = true;
}
cout << answer.size()<<'\n';
sort(answer.begin(), answer.end());
for (auto& ele : answer) cout << ele << '\n';
}
빠져나올 수 없는 시간 초과의 늪... + 10으로 나눈 나머지를 출력하라는 데 바보 같이 그냥 출력하고 있었음.
문제를 꼼꼼히 읽자...ㅎㅎ 처음에는 무작정 BFS로 짰다가 계속 시간초과가 나길래 (구글의 도움을 빌려서) 코드를 수정했다. 찾아보기로는 플러드 필이라는 알고리즘 구현을 요구하는 문제라고 한다. 처음 듣는 알고리즘이라 해당 알고리즘에 대해서는 나중에 별도로 정리해봐야겠다.
1. 인접해 있는 0을 묶어서 그룹 인덱스를 붙임
2. 해당 그룹에 0이 총 몇 개가 포함되어있는지를 저장하는 딕셔너리 생성
3. 보드를 돌 때마다 1을 만나면 상하좌우 그룹의 0 개수를 전부 더해서 출력(2번의 딕셔너리 이용)
위의 설명은 직관적으로 와닿지 않을 수도 있으니 아래 코드의 주석으로 자세히 설명하겠다.
(1) 초기화 및 설정
N, M = map(int, input().split())
board = [list(map(int, sys.stdin.readline().strip())) for _ inrange(N)]
visited = [[0for _ inrange(M)] for _ inrange(N)]
zeros = [[0for _ inrange(M)] for _ inrange(N)]
board : 전체 맵
visited : BFS를 통해 이미 방문했는지, 아닌지 확인
zeros : 인접한 0끼리 같은 그룹으로 묶어서 표시
(2) BFS - 그룹표시
group = 1
info = {}
for i inrange(N):
for j inrange(M):
ifnot board[i][j] andnot visited[i][j]: #0인 칸이고 아직 방문하지 않은 노드이면
cnt = BFS(i, j) #BFS수행해서 인접한 0의 개수 리턴
info[group] = cnt #{index: cnt} 꼴로 삽입
group += 1#그룹 인덱스 갱신
group : 그룹 인덱스
info : {index: cnt} 형태의 딕셔너리. 각 그룹에 포함된 0의 개수 저장
아직 방문하지 않은 0인 칸마다 BFS수행해서 그룹 인덱스 표시해주고, 그룹별 0의 갯수 딕셔너리에 추가
