골드 정복기 (gold 5~3)

실력 상승을 위해 골드 5~3 랜디를 해보았다. 효과는 있는 거 같기도..

대충 어디가서 꿀리지 않을 정도로만 잘해지면 될 거 같다.

---

BOJ 2024 - 선분덮기

 

태그: 스위핑, 그리디

 

현재 정점을 덮을 수 있는 선분 중 왼쪽으로 가장 길게 뻗은 선분을 선택하면 된다.

0번 정점부터 시작해 이동하며 갱신해 준다. 

범위 잘못 잡아서 많이 틀렸던..

---

BOJ 23889 - 돌 굴러가유

 

태그: 그리디, 정렬 +누적합

 

간단하게 생각하면 쉽게 풀이를 얻을 수 있었다. 돌이 시작하는 지점들 사이의 합을 구해둔 뒤 그중 구간의 합이 가장 큰 k개를 선택해 주면 된다. 

---

BOJ 1633 - 최고의 팀 만들기

 

태그: dp

 

3차원 dp에서 반복문으로 테이블 전이 시키는 과정이 조금 힘들었다. dp의 길은 끝이 없고..

dp테이블을 다음과 같이 정의하자.

dp[i][w][b]:=i번째 선수까지 봤을 때 백 팀이 w명이고 흑 팀이 b명일 때 최대 능력치의 합

이제 처음 선수를 흑, 백팀에 넣거나 넣지 않는 경우로 테이블을 초기화해 주고 n번째 까지 전이시켜 주면 된다.

dp[i][w][b]=max(dp[i][w][b],dp[i-1][w][b],dp[i-1][w-1][b]+i번째 선수의 백 능력,dp[i-1][w][b-1]+i번째 선수의 흑 능력)

 

테이블 상태를 잘못 관리해서 생각보다 오래 걸렸다.

---

BOJ 28218 - 격자 게임

 

태그: dp, 게임이론

 

무려 KOI기출문제다. 

이런 류의 문제를 푸는 방법을 알았다면 입상했을 텐데.. 아쉬운 부분이다.

dp테이블을 다음과 같이 정의하자.

dp[i][j]:=(i,j)위치에서 선공/후공 승리

(n,m)의 위치에서는 선공이 움직일 수 없어진다. 그렇기 때문에 (n,m)에서 반대로 테이블을 채워나가면 된다.

채우는 과정은 선공이 패배하는 상태에서 다음 상태에 전이시킨다. 

점화식을 적기 귀찮으니 코드로 대신한다.

for(int i=n-1; i>=0; i--){
        for(int j=m-1; j>=0; j--){
            if(dp[i][j]==1 or arr[i][j]=='#')continue;
            if(i-1>=0)dp[i-1][j]=1;
            if(j-1>=0)dp[i][j-1]=1;
            for(int c=1; c<=k; c++){
                if(i-c<0 or j-c<0)break;
                dp[i-c][j-c]=1;
            }
        }
    }

총 시간복잡도는 O(nmk)이다.

 

맞왜틀을 좀 많이 당한 문제였다.

---

BOJ 1354 - 무한 수열 2

 

태그: dp

 

n제한이 크기 때문에 hash map을 사용하자. 문제에서 제시한 점화식을 그대로 적용해서 탑다운 방식으로 dp를 짜면 된다.

---

BOJ 16888 - 루트 게임

 

태그: dp, 게임이론

 

격자 게임처럼 1부터 상태전이를 시작하면 된다.

dp[0]=0;
dp[1]=1;
dp[2]=0;
for(int i=0; i<1010101; i++){
    if(dp[i])continue;
    for(int j=1; i+j*j<1010101; j++){
        dp[i+j*j]=1;
    }
}

---

BOJ 25330 - SHOW ME THE DUNGEON

 

태그: 백트래킹

 

어렵지는 않은데,, 커팅을 잘해야 한다.

평범하게 짜면 O(n!)이라 현재 재귀에서 사람 수가 최댓값보다 작으면 리턴, 체력이 0이면 리턴하는 식으로 여러 번 커팅을 해주면 된다.

---

BOJ 20035 - 이동하기 5

 

태그: 그리디

 

문제 힌트에 오류가 있는 요상한 문제다.

가로를 지나갈 때 얻는 사탕의 개수와 세로를 지날 때 얻는 사탕의 개수는 일정하기 때문에 그리디 하게 접근할 수 있다.

수열 a의 최댓값을 찾고 최댓값이 처음 나타나는 인덱스와 마지막으로 나타나는 인덱스를 저장한다. 최댓값이 나타나는 구간에서 가로로 지나가면 a의 최댓값을 더 얻을 수 있다. 이를 통해 수열 a에서 얻을 수 있는 사탕의 개수가 최대가 됨을 알 수 있다. a에 따라 b의 값은 정해지므로 이를 잘 구현하면 문제를 풀 수 있다. 

---