침대 밖은 위험해!

문제출처 : https://www.acmicpc.net/problem/2193

1. 문제요약

- 0과 1로 이루어진 수 중에 0으로 시작하지 않고 1이 두번 연속으로 나타나지 않는 수를 이친수

- 1, 10, 101 등은 이친수

- 01, 110 은 이친수가 아님

- n자리 이친수의 갯수는?

- 1 <= n <= 90

2. 접근방법

- n자리 이진수를 브루트 포스로 다 확인할 수 없음.

- n자리가 0이면, n-1 자리는 0, 1

  n자리가 1이면, n-1 자리는 0

- d[n][i] 를 n자리수, 마지막 수가 i인 이친수의 갯수라고 하면

  d[n][0] = d[n-1][0] + d[n-1][1]

  d[n][1] = d[n-1][0]

- 조금만 더 생각을 해보면

- n자리가 0이면, n-1 자리는 0, 1

  n자리가 1이면, n-1 자리는 무조건 0 이므로 n-2 자리에 0, 1

- d[n] 을 n자리수 이친수의 갯수라고 하면

  d[n] = d[n-1] + d[n-2]

  피보나치

3. 시간복잡도

- n

4. 회고

- 이친수의 갯수가 int형을 넘을 수 있으므로 long long

소스코드

#include<iostream>
using namespace std;

int n;
long long d[100] = { 0, 1 };

int main(void){
	cin >> n;
	for (int i = 2; i <= n; i++){
		d[i] = d[i - 1] + d[i - 2];
	}
	cout << d[n] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/11057

1. 문제요약

- 33455, 012345와 같이 각 자릿수가 오름차순인 수를 오르막 수라 함.

- 인접한 수가 같아도 오름차순으로 인정

- 9111 과 같은 수는 오르막 수가 아님

- 수는 0으로 시작 할 수 있음

- 오르막 수의 갯수는?

- 1 <= n <= 1,000

2. 접근방법

- n자릿수가 1000 이므로 모든 수를 다 확인 할 수 없음

- n 자릿수의 마지막 수가 0 이면, n-1 자릿수의 마지막 수는 0

  n 자릿수의 마지막 수가 1 이면, n-1 자릿수의 마지막 수는 0, 1

  n 자릿수의 마지막 수가 2 이면, n-1 자릿수의 마지막 수는 0, 1, 2

  ...

- 필요한 항목은 자릿수, 마지막 수 이므로

- d[n][j] : n 자릿수, 마지막 수가 j인 오르막 수의 갯수

- d[n][j] = d[n-1][0] + d[n-1][1] + ... + d[n-1][j-1] + d[n-1][j] = ∑(i=0, j) d[n-1][i]

3. 시간복잡도

- n

4. 회고

- 10007의 나머지 이므로 n이 1000 이라 해도 1000자릿수의 10007의 나머지 합이 int 범위를 넘어 갈 수 없음

소스코드

#include<iostream>
using namespace std;

int n, d[1001][10], ans = 0;

int main(void){
	cin >> n;
	for (int i = 0; i < 10; i++) d[1][i] = 1;
	for (int i = 2; i <= n; i++){
		for (int j = 0; j < 10; j++){
			for (int k = 0; k <= j; k++){
				d[i][j] += d[i - 1][k];
			}
			d[i][j] %= 10007;
		}
	}
	for (int i = 0; i < 10; i++) ans += d[n][i];
	cout << ans % 10007 << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/10844

1. 문제요약

- 45656 은 인접한 모든 자리수의 차이가 1 이를 계단수라 함

- n 자리수의 계단수의 갯수는?

- 한자릿수는 9개

2. 접근방법

- 100 자릿수 이므로 브루트 포스는 못함

- dp를 활용

- n-1 자릿수의 마지막 수가 0 이면, n 자릿수의 마지막 수는 -1, 2 인데 -1은 아니므로 2

  n-1 자릿수의 마지막 수가 1~8이면, n 자릿수의 마지막 수는 n-1의 마지막 수 -1, +1

  n-1 자릿수의 마지막 수가 9 이면, n 자릿수의 마지막 수는 8, 0 인데 0은 아니므로 8

- dp에 필요한 항목은 '자릿수', '마지막수'

- d[n][j] : n 자릿수의 마지막 수가 j인 갯수

- 일반적으로 d[n][j] = d[n-1][j-1] + d[n-1][j+1]

3. 시간복잡도

- n

4. 회고

- d[n][j] = d[n-1][j-1] + d[n-1][j+1] 을 j가 0일 때와 9일때로 나누지 않은 이유는

  전역변수로 선언시 d[n][-1] 은 0으로 해주기 때문(음수 인덱스)

- 정답이 1,000,000,000 로 나눈 나머지 이므로 d[n][0] ~ d[n][9] 까지의 합이 int 범위를 넘어 갈 수 있으므로

  ans는 long long으로 선언

- d[101][11]이 아닌 d[101][10] 으로 선언하면 d[n][10] 인경우 인덱스가 넘어가서 다른 값이 나옴

소스코드

#include<iostream>
using namespace std;

int n, d[101][11];
long long ans = 0;

int main(void){
	cin >> n;
	for (int i = 1; i < 10; i++) d[1][i] = 1;
	for (int i = 2; i <= n; i++){
		for (int j = 0; j < 10; j++){
			d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % 1000000000;
		}
	}
	for (int i = 0; i < 10; i++) ans += d[n][i];
	cout << ans % 1000000000 << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/9095

1. 문제요약

- 주어진 정수를 1, 2, 3 의 합으로 나타내는 방법의 수는?

- 1 <= n <= 11

- 4를 1, 2, 3의 조합으로 나타내는 방법 7가지

  1 + 1 + 1 + 1

  1 + 1 + 2

  1 + 2 + 1

  2 + 1 + 1

  2 + 2

  1 + 3

  3 + 1

2. 접근방법

- 임의의 정수 n을 1, 2, 3의 조합으로 나타내는 가짓수는

  n-1을 1, 2, 3의 조합으로 나타내는 가짓수 +

  n-2를 1, ,2, 3의 조합으로 나타내는 가짓수 +

  n-3을 1, 2, 3의 조합으로 나타내는 가짓수

- d[n] : n을 1, 2, 3의 조합으로 나타내는 가짓수 로 정의한다면

  d[n] = d[n-1] + d[n-2] + d[n-3]

3. 시간복잡도

- n

4. 회고

- 문제를 분할, 임의의 수에서 문제를 잘게 쪼개 보자

소스코드

#include<iostream>
using namespace std;

int t, n, d[11] = { 0, 1, 2, 4 };

int main(void){
	for (int i = 4; i < 12; i++)
		d[i] = d[i - 1] + d[i - 2] + d[i - 3];
	cin >> t;
	while (t--){
		cin >> n;
		cout << d[n] << "\n";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/11727

1. 문제요약

- 2xn 크기의 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수는?

- 1 <= n <= 1,000

- 10007로 나눈 나머지를 출력

2. 접근방법

- 2xn 도형을 채우는데 n번째에 올 수 있는 모형의 종류는

  세로 1x2 1개

  가로 2x1 2개

  정사각형 2x2 1개

  가 올 수 있음

- d[n]을 2xn 모형을 채우는 경우의 수 라고 하면

  d[n] = d[n-1] + 2 * d[n-2]

3. 시간복잡도

- n

4. 회고

소스코드

#include<iostream>
using namespace std;

int n, d[1001] = { 0, 1, 3 };

int main(void){
	cin >> n;
	for (int i = 3; i <= n; i++){
		d[i] = d[i - 1] + 2 * d[i - 2];
		d[i] %= 10007;
	}
	cout << d[n];
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/11726

1. 문제요약

- 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수는?

- 1 <= n <= 1,000

- 10007로 나눈 나머지를 출력

2. 접근방법

- 2xn 도형을 채우는데 n번째에 올 수 있는 모형의 종류는

  세로 1x2 1개

  가로 2x1 2개

  가 올 수 있음

- d[n]을 2xn 모형을 채우는 경우의 수 라고 하면

  d[n] = d[n-1] + d[n-2]

  피보나치

3. 시간복잡도

- n

4. 회고

- 모듈러 연산 : https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction

소스코드

#include<iostream>
using namespace std;

int n, d[1001] = { 0, 1, 2 };

int main(void){
	cin >> n;
	for (int i = 3; i < n + 1; i++){
		d[i] = d[i - 2] + d[i - 1];
		d[i] %= 10007;
	}
	cout << d[n] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/1463

1. 문제요약

- 연산1. 3으로 나누어 지면 3으로 나눔

  연산2. 2로 나누어 지면 2로 나눔

  연산3. 1을 뺌

- 위 연산 3가지를 이용하여 N을 1로 만드는 최소 횟수

- 1 <= N <= 10^6

2. 접근방법

- bfs

  N에서 N/3, N/2, N-1을 1을 만날때 까지 bfs

=> N과 N이 1로 가는 모든 과정들이 2나 3으로 무조건 나누어 떨어진다고 하면,

     N -> N/3, N/2, N-1 3개의 숫자로 뻗어나감(큐에 3개씩 저장)

     방문한 숫자는 다시 방문할 필요가 없으므로 10^6 만큼 시간이 걸림

     (물론 1을 만나자마자 bfs를 그만 두면 좀 더 빠를거임)

- dp

  N이 1이 되는 최소 횟수는 N/3, N/2, N-1 중에 최솟값 + 1

  d[n] : n이 1이 되는 횟수 로 정의한다면

  d[n] = min(d[n-1], d[n/2], d[n/3]) + 1

3. 시간복잡도

- bfs나 dp 모두 최악 N

4. 회고

- d[n] + 1 을 안해줘서 한참 고민했네...

소스코드 : dp bottom up

#include<iostream>
using namespace std;

int n, d[1000001] = { 0, 0, 1, 1 };

int main(void){
	cin >> n;
	for (int i = 4; i < n + 1; i++){
		d[i] = d[i - 1];
		if (i % 2 == 0) d[i] = d[i] > d[i / 2] ? d[i / 2] : d[i];
		if (i % 3 == 0) d[i] = d[i] > d[i / 3] ? d[i / 3] : d[i];
		d[i]++;
	}
	cout << d[n] << "\n";
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/2573

1. 문제요약

- 물과 상하좌우 4방향으로 인접한 빙하는 접하는 면 갯수 만큼 1년 뒤 녹음

- 빙하가 두 덩어리 이상으로 분리되는 최초시간

- 빙하가 다 녹을 때 까지 두 덩어리 이상으로 분리되지 않는다면 0 출력

- 3 <= 행n, 열m <= 300

- 첫행, n-1행, 첫열, m-1열은 0으로 주어짐

- 빙하의 최대 갯수는 10,000 이하

2. 접근방법

- 빙하 갯수를 세는 dfs or bfs

- 맵을 돌면서 물이 접하고 있는 빙하를 -1

3. 시간복잡도

- 빙하 갯수를 세는 dfs : N*M

- 맵을 돌면서 물이 접하고 있는 빙하 -1 : N*M

  => 여기까지 2NM

- 위 두 과정을 최대 몇번이나 반복할까?

  빙하의 갯수는 최대 10000 = 25 * 40

  행 25, 열 40 으로 된 한 덩어리의 빙하가 가장 늦게 녹음. 물과 접하는 면이 가장 작기 때문(50 + 80)

  정중앙에 있는 빙하가 가장 늦게 녹을 텐데 여기까지 도달하기 위해서는 12행((25 - 1) / 2)이 녹아야함

  모든 빙하가 10이라고 한다면 대략 한 행이 녹는데 10년

  12행이 녹는데 120년

  => 120 * 2NM = 21,600,000 반복

  => 반복마다 코드 길이가 조금 되지만 시간내엔 들어옴

4. 회고

- dfs를 돌때 4방향 탐색을

  if(!map[r-1][c] && !check[r-1][c]) dfs(r-1, c);

  if(!map[r][c-1] && !check[r][c-1]) dfs(r, c-1);

  if(!map[r+1][c] && !check[r+1][c]) dfs(r+1, c);

  if(!map[r][c+1] && !check[r][c+1]) dfs(r, c+1);

  은 틀리고

  for(int k = 0; k < 4; k++){

int nr = r + dr[k];

int nc = c + dc[k];

if(!map[nr][nc] && !check[nr][nc])

dfs(nr, nc);

  }

  는 맞는거지??

  물론 중간에 빙하 깍는 과정을 조금 수정했지만 디버깅 하면서 둘다 잘 돌아갔는데

  으흠.... 

  한시간동안 뻘짓했는데

- 시간이 244ms 나왔는데 더 줄일 수는 없을까?

- dfs에서 2개 이상 발견하면 dfs 안돌고 탈출

- 다 녹은 빙하 위치를 기억해서 다음 시작점을 거기서 부터 녹여나가도

소스코드

#include<iostream>
using namespace std;

int n, m, year, block;
int map[305][305];
bool check[305][305];
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };

void dfs(int r, int c){
	check[r][c] = true;
	for (int i = 0; i < 4; i++){
		int nr = r + dr[i];
		int nc = c + dc[i];

		if (map[nr][nc] && !check[nr][nc])
			dfs(nr, nc);
	}
}

int main(void){
	cin >> n >> m;
	char a;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];

	while (true){
		block = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				check[i][j] = false;

		for (int i = 1; i < n - 1; i++)
			for (int j = 1; j < m - 1; j++)
				if (map[i][j] && !check[i][j]){
					block++;
					dfs(i, j);
				}

		if (block >= 2){
			cout << year << "\n";
			return 0;
		}
		else if (block == 0) {
			cout << 0 << "\n";
			return 0;
		}

		year++;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (!map[i][j] && !check[i][j])
					for (int k = 0; k < 4; k++){
						int nr = i + dr[k];
						int nc = j + dc[k];

						if (0 <= nr && nr < n && 0 <= nc && nc < m && map[nr][nc]){
							map[nr][nc]--;
						}
					}
	}
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

이번편은 번외편으로 게임 진행에 있어서 도움이 될만한 자료입니다.

1. 경험치 추가획득 방법

- 레벨이 7, 8 언저리 쯤 되면 경험치 쌓기가 힘든데 조금이라도 경험치를 더 쌓는 방법을 알려드리겠습니다.

1) The Three 제단 이용하기

- 어떤 마을이던 The Three의 이렇게 생긴 제단이 있을 겁니다.

- 제단을 누르면 100gold와 500gold 기부가 있습니다.

- 100gold를 기부하면 게임시간 일주일 동안 몬스터를 잡을때 +3%의 경험치를 추가로 주는 축복(?)을 받을 수 있습니다.

- 500gold를 기부하면 게임시간 일주일 동안 몬스터를 잡을떄 +5%의 경험치를 추가로 주는 축복(?)을 받을 수 있습니다.

- 상세정보를 보면 XP 보너스에 +2%에 +5%가 추가로 붙은게 보이는군요

2) 스크롤 이용하기

- 파밍이나 상점에가면 'Scroll of Lesser Wisdom' 이 있습니다.

- 이걸 사용하면 게임시간 2일 동안 7%의 경험치를 추가로 얻을 수 있습니다.

- 위 사진은 Scroll of Lesser Wisdom 이네요

- 스크롤은 3종류가 있는데

  Scroll of Lesser Wisdom : 2day +7%

  Scroll of Wisdom : 2day +10%

  Scroll of Greather Wisdom : 2day +15%

  입니다.

- 정리하자면

  The Three 제단

  : 100gold : 7days +3%

  : 500gold : 7days +5%

  스크롤

  : Scroll of Lesser Wisdom : 2day +7%

  : Scroll of Wisdom : 2day +10%

  : Scroll of Greather Wisdom : 2day +15%

- The Three 제단에 500gold 짜리가 가성비가 좋아서 전 항상 시간될 때 마다 받아서 가네요

2. 아이템 속성

- 아이템에 보면 위 사진처럼 파란색 글씨가 있는 것들이 있습니다. 물론 방어구나 악세사리도요.

- 그거에 대해 정리해보겠습니다.

1) 무기

- '랭크' 라고 적은 부분은 위 아이템에 보면 'Orc Slayer 2' 라고 적혀 있는데 2가 랭크 입니다.

※ Light 는 무기 타입 입니다. 2-Handed, Hand, Ranged와 같은.. 속성이 아닙니다. 

2) 방어구, 악세사리

3. 어드밴스드 스킬

- 어드밴스드 스킬이 35개라 너무 많으니 다음 기회에......

앞서 North Bluemist River 마을 퀘스트를 깼습니다.

2017/12/22 - [일상다반사/게임] - Exiled Kingdoms 공략 - Lannegar Valley, Lannegar(City) 1

2017/12/25 - [일상다반사/게임] - Exiled Kingdoms 공략 - Lannegar Valley, Lannegar(City) 2

2018/01/02 - [일상다반사/게임] - Exiled Kingdoms 공략 - North Bluemist River

이번편은 앞편 A Wild Mystery 를 진행하러 가는 도중 들렸던 'Rhoneis(City)' 마을 퀘스트에 대해 쓰겠습니다.

해당편 퀘스트 순서

- Shaking Bones

- A safe bet

- Lannegar Valley(City)의 Gather ingredients

1. Rhoneis Plains, Rhoneis(City)

- 오늘 퀘스트를 수행할 장소 입니다.

- North Bluemist River에서 A Wild Mystery 퀘스트를 수행하기 위해 지나가다가 'Captain Teara'에게 'Coyote Hunt' 퀘스트를 받은 곳입니다.

2. 추천 퀘스트 순서 및 퀘스트 획득, 클리어 방법

1) Shaking Bones

- Rhoneis(City) 지도 입니다. 잘 안보이지만 오른쪽 위 구석에 '3' 에 'Brother Gudazar' 에게 갑니다.

- 'Shaking Bones' 퀘스트를 받고 처음부터 모았던 해골 12개를 창고에서 꺼내서 주면 끝입니다.

※ 만약 해골을 구해야 한다면

1) Lannegar Valley의 'Ydaya Tomb'

2) North Bluemist River의 'Kleyou Tomb'

3) Rhoneis Plains 아래 맵의 'Deadwood'

에서 구하면 됩니다.

2) A safe bet

- 해당 퀘스트를 수행하기 위해서는 5레벨 이상이 되어야 받을 수 있습니다.

- 미노 잡기가 힘드시다면 좀 더 레벨링 이후 잡는걸 추천합니다.

- Rhoneis(City) 지도에서 '6' 에 'Therod Nom' 에게 가서 퀘스트를 받습니다.

- 미노타우르스는 'Rhoneis Plains' 에서 서쪽 방향에 있는 'Northern Jabal Hills'로 갑니다.

- 'Northern Jabal Hills' 맵에서 서쪽으로 쭉 가다보면 위 맵에 표시된 곳에 미노타우르가 간간히 있고 그 안쪽으로 'Maze of Lamth' 던전안에 서식합니다.

- 'Maze of Lamth' 던전의 지도 입니다. 아직은 다 돌만한 레벨이 안되고 트랩도 많기 때문에 앞부분에서만 조심히 'Minotaur Horn'를 구할때 까지만 돌면됩니다.

- 물론 던전에 안들어 가고 밖에있는 미노를 잡아도 됩니다.

※ 시크릿 도어는 나중에 다시 이 던전에 올 일이 있으니 그때 열겠습니다.

- 왼쪽 사진처럼 뿔 하나를 구해서 가져다주면

- 오른쪽 사진처럼 'Lionskin Cuirass' 를 얻습니다.

- 'Lionskin Cuirass' 는 초반에 괜찮기 때문에 다른 갑옷을 구하기 전까지는 쓸 수 있습니다.

- 이번 퀘스트로 'Rhonies(City)' 에서 받을 수 있는 퀘스트 3개를 클리어 했습니다.

3) Lannegar Valley(City)의 Gather ingredients

- Red Orchid 퀘스트 내용을 잘 읽어보면 'Bluemist River'의 bank 에서 구할 수 있다고 합니다.

- wiki를 참조하면 'Kings Bridge'와 'New Garand's Farmlands' 에서 구할 수 있다고 합니다.

  (New Garand 였군요.. New Grand 인줄 알았는데..)

- 위 사진에 표시한 두 부분 입니다.

- 저는 Kingsbridge 두 곳에서 발견했습니다.

- 왼쪽은 강 윗부분이고 오른쪽은 강 아랫부분이네요

※ 팁

    꼭 하나 더 주워 놓으세요. 나중에 'Eye of the Tiger' 퀘스트를 깨는데 하나 필요합니다.

    나중에 찾을려면 잘 안보이니까요

- 'Red Orchid'를 줍줍하고 'Lannegar(City)'의 'Alchemist Markus'에게 가져다 줍니다.

- 가져다 주면 이젠 'Luminescent Fungus'를 가져오라고 합니다.

- 이전 퀘스트를 깨면서 동굴형 던전을 돌다보면 버섯 주울 수 있다고 말씀드렸는데 그거 가져다 주면 해당 퀘스트는 끝나게 되고 

  퀘스트 보상으로 포션을 만들 수 있습니다.

- 사실 돈주고 사는게 편해서 굳이 모아서 만들어 보진 않았네요...

- 조합을 알려드리자면

  1) 60hp를 채워주는 힐링 포션

     : Blue Orchid x1

     : Red Orchid x1

     : 100gold

  2) 12초 동안 방어력을 10 올려주는 포션

     : Luminescnet Fungus x1

     : Deadweed x1 (이건 Deadwood나 New Garand's Farmlands 맵에 가면 카우보이 영화에 나오는 굴러다니는 먼지처럼 생긴게 있습니다.)

     : 100gold

- 이로써 Gather ingredients 퀘스트도 마무리 되었습니다.

- 'Lannegar(City)' 에서 수행할 수 있는 퀘스트는 'Where is Giles' 빼고 끝났네요

  'Where is Giles' 퀘스트는 'Varsilia' 의 명성이 'heroic' 이상이 되어야만 받을 수 있기 때문에 다른 퀘스트를 깨면서 명성을 쌓도록 합시다.

다음편

- Kings Bridge에서 받을 수 있는 퀘스트와 메인퀘스트를 진행하도록 하겠습니다.

- The best plan

- Find constanze

- Forgotten Lore

- An initiate's end

- Prisoner of Orcs

너무 기니 두편으로 나눌 것 같네요

번외편

- Three 제단에 기부하고 경험치 더 받기

- 아이템 속성

- 어드밴스드 스킬