침대 밖은 위험해!

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

1. 문제요약

- 중요도에 따라 인쇄순서를 결정하고 특정 문서가 몇번째 출력되는가?

- 문서의 수 N <= 100, 0 <= 위치 M < N

2. 접근방법

- 일단 N이 얼마 안되기 때문에 브루트 포스

- 모든 문서가 큐에 저장

- 큐에 첫번째 문서가 출력 대상이 아니라면 뒤로 보냄

- 출력 대상이라면 출력

3. 시간복잡도

- Queue나 배열 하나만 쓴다면 N^3,

  출력 대상을 찾는데 하나의 문서와 모든 문서를 비교 해야 하므로 N^2, 

  모든 문서의 개수가 N 이므로 N^3

- Priority_Queue 라던가 가중치를 가지고 있다면,

  하나의 문서를 찾는데 N, 문서 전체의 개수가 N 이므로 N^2

4. 회고

- 배열을 큐처럼 만들어서 출력 대상이 아니면 배열 뒤에 붙이는 방식인 경우 최소 100 * 101 / 2 = 5050 이상 사이즈가 필요

- 인덱스만 가지고 움직인다면 배열 사이즈는 N이면 됨

  출력한 놈을 다시 출력하는 논리적 오류가 발생

  이런거 신경 안쓸려면 index를 출력한놈은 건너 뛰게 만들어야함

- 문서 번호와 문서 중요도를 보관해야 함

- 배열로 구현 했을 때 한칸씩 당기지 않으면 출력 했는지 안했는지 체크가 필요

- Queue 자료구조를 쓴다면 front를 뺄 때, 다른 자료와의 중요도를 비교할 수 있는 수단이 필요함

  하나씩 빼서 비교하던가 아니면 Priority_Queue나 중요도를 저장하고 있는 다른 배열과 비교가 필요

소스코드 : N^3

#include<iostream>
using namespace std;

int main(void){
	int t;
	cin >> t;
	while (t--){
		int n, m, q[101], check[101] = { 0 };
		cin >> n >> m;
		for (int i = 0; i < n; i++)
			cin >> q[i];

		int index = 0, cnt = 1;
		while (cnt <= n){
			if (index == n) index = 0;

			int i = 0;
			for (; i < n; i++){
				if (!check[i] && q[index] < q[i])
					break;
			}
			// !check[index]가 없다면 출력한 놈을 다시 출력하게 함
			// 예제에서 정답은 맞아도 중간 값이 틀림 => 결국은 틀림
			if (!check[index] && i == n){
				check[index] = cnt;
				cnt++;
			}

			index++;
		}

		cout << check[m] << "\n";
	}
	return 0;
}

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

Lannegar Valley, Lannegar(City)의 퀘스트 초반부는 앞글 참조

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

해당편 퀘스트 순서

- The seed of trust : 보디가드

- Head Hunting : 고블린 왕 모가지 따기

0. 길가 상인, 길가 도둑, 창고만들기

- 길가 상인 1 - 무기, 기타 판매자

  : 날이 어두어 진 뒤에 길에 다니다 보면 이런 보따리 장사꾼을 만날 수 있는데 궁금하면 봐도 되고 아니면 그닥 필요는 없으니 넘겨도 됩니다.

- 길가 상인 2 - 가죽 구입자

  : 보따리 장사와 마찬가지로 날이 어두어졌을 때만 길에서 랜덤으로 만날 수 있습니다. 성직자로 새로 플레이하면서 한번 만났네요..

  : 초반에 돈을 왕창 벌 수 있는 아주 좋은 수단입니다.

  : 가죽은 다 팔지 말고 5장 정도는 남겨둡니다. 다음 퀘스트때 재료로 사용되므로 다시 구할려면 맵을 뛰어다는 귀찮은 일이 발생합니다.

- 길가 도둑

  : 길거리 상인과 마찬가지로 날이 어두어졌을 때만 만날 수 있습니다. 마찬가지로 랜덤이구요

  : 만나면 피가 엄청 없는 경우를 제외하고는 잡을 수 있으니 잡도록 합니다. 경험치와 템을 주니까요

  : 만약 잘 못 선택해서 싸워야 하는데 질거 같으면 마을로 도망갑니다. 마을 문지가가 다 죽여줍니다.

- 창고만들기

  : 아무 마을에서나 깃발 달린 집을 찾습니다.

  : 'Vault'를 누르면 4칸이 있는데 왼쪽 위칸을 누르면 '1000'gold에 개설 가능합니다. 

  : 초반 퀘스트와 잡템을 처분하면 1000gold 이상은 모이니 하나 정도는 뚫어둡니다.

  : 그래야 잡템들을 모아놓고 나중에 퀘스트 깰때 꺼내서 바로바로 클리어 가능합니다.

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

ㄹ) The seed of trust

- 보디가드 해주기 입니다.

- 마을에서 'Rodney'를 찾아서 보드가드를 해준다고 합니다.

- (오른쪽 그림처럼 'Journal'에서 확인 가능합니다.)

- 왼쪽 그림처럼 표시된 곧으로 가서 서쪽 맵으로 넘어 가도록 합니다.

- 거기서도 서쪽으로 계속 달리다 보면 오른쪽 맵처럼 작은 마을이 나오는데 거기까지 데려다 주면 됩니다.

http://www.exiledkingdoms.com/wiki/index.php?title=The_seed_of_trust

- wiki를 꼭 참조하세요. 대답에 따라 약간이지만 보상이 달라집니다.

- 처음 이 게임 할 때 온갖 NPC 다 잡고 다녔더니 마을에 발도 못붙이는 상황이 벌어졌드랬죠........

ㅁ) Flesh is Weak + Forgotten Lore

- 좀비 가죽 모으기 입니다.

- 마을 'Three' 라는 교단자인 'Brother Janus' 에게 가서 퀘스트를 받으면 오른쪽 그림처럼 'zombie flesh'를 3개 가져오라고 합니다.

※ 팁 : 퀘스트를 받기 전에 'Three' 가 무엇이냐 라고 묻고 3개의 질문 목록이 나오는데 하나씩 다 하게 되면 '40xp'를 받을 수 있습니다.

- 왼쪽 그림처럼 퀘스트를 확인 합니다.

- 오른쪽 맵에서 남동 방향으로 보이는 검은색으로 가려진 돌들이 보이는데 그곳에 던전이 있습니다.

- 가시기 전에 이쯤 되면 3레벨 쯤 되고 돈도 조금 있을 텐데 방어구를 사서 아이템을 맞추고 가는 것을 추천 드립니다.

- 좀비가 3레벨 쯤이니 원활한 좀비 사냥과 다니다가 트랩 밟고 죽으면 스트레스가 폭발할테니까요

- 맵 입구에 가면 'Anton Gerdt' 이란 "Loreseeker'가 있습니다. 

- 아주 좋은 퀘스트 이므로 꼭 내가 자네 성물?? 3개를 찾아 주겠다고 하고 퀘스트를 수락 받습니다.

※ 팁 : 던전에서는 저장이 안되므로 꼭 들어가기 전에 저장을 해주고 들어가세요

         신나게 돌다가 죽으면 휴대폰을 던질지도 모릅니다.

- 트랩 입니다........ 알림창에 따르면 저거 밟았다고 피가 21이 날아 갔네요....

- 'Ydaya Tomb'의 전체 맵입니다.

- 왼쪽 위 1번과 오른쪽 상단 2번이 secret door 이므로 꼭 무조건 들어가시길 바랍니다.

- Flesh is Weak는 길에 다니는 좀비 죽이면 가죽 나오니 줍줍하면 되고

- Forgotten Lore는 위 맵에서 좌측 아래 3번 시체까지 가야만 하는데 몹이 좀 많습니다.

- 한마리 씩 잘 꿰어서 둘러싸이지 않고 잡도록 합니다.

※ 팁 : 몹이 여러마리가 달려오면 한번에 상대하기 벅차므로 문이나 좁은 골목을 이용하도록 합니다. 그러면 몹들이 한줄로 서게되고 뒤에 몹은 리치가 짧아 나한테 데미지를 줄 수 없기 때문에 한마리씩 상대가 가능합니다.

죽을거 같으면 던전 밖으로 나가면 '전투 중'이 없어지기 때문에 힐(2번 주어지는, 성직자 힐 제외) 사용이 가능합니다. 단, 몹이 문앞에 까지 따라 오므로 들어갔을때 몹이 문 앞에서 대기 타고 있습니다. 조심하세요

스켈레톤을 잡았을때 떨어지는 'Skull'은 12개가 될 때 까지 모아두세요. 다음 퀘스트에 필요합니다. 12개 이상은 필요없으니 팔아도 됩니다.

- 왼쪽사진은 '1번 secret door' 입니다.

- 오른쪽 사진은 '2번 secret door' 입니다.

※ 팁 : 워리어나 성직자는 저 문 찾는게 확률이 낮기 때문에 힘들겁니다. 그럼 마을 포션 상인한테 가면 'Scroll of Detection' 을 파는데 75% 확률로 비밀문이나 트랩을 찾아 줍니다. 한번에 성공한다는 보장이 없기 때문에 문 하나 찾는데 2장 정도 필요하니 4장 정도 챙겨 갑니다.

- 1번 비밀문은 그냥 뚫고 들어가서 잡으면 됩니다.

- 2번 비밀문 안에는 'Librarian(Weak)' 란 왠 미친 몬스터가 서식 중이니 만반의 준비가 필요합니다.

- 퀘스트를 받으면서 'Potion of Death Ward' 란 포션을 받았을 겁니다. 문열면 바로 달려나오기 때문에 미리 먹어두고 문을 열고 잡도록 합니다.

- 잘 보면 'Librarian(Weak)'의 'Resistances'가 화염, 빙결은 -25 / 번개는 -40 입니다. 이런 속성으로 때려 잡으면 데미지가 더 들어가기게 잡기 쉽습니다.

※ 팁 : 지금 깨기 힘들면 조금 나중으로 미뤄도 됩니다. 고블링 킹 모가지 따오면 번개 속성 무기를 주기에 그거 들고 잡으면 좀 더 수월 합니다.

- 잡았다고 방심하지 마세요. 트랩이 있습니다.

- 책 말고 시체 위로 가면 'shelf' 라는 책창이 있는데 꼭 먹으세요. 한 번밖에 못 먹기 때문에 두 번 들어갈 필요는 없습니다.

- 선반에서 총 4개의 아이템을 먹는데 바지는 좋으니까 입으면 되고 'Ancient Tolassian Tome' 이란 책을 얻는데 사용하면 스탯 1포인트 줍니다.

- 아주 좋습니다.

- 우선 좀비 가죽 3개를 모으면 Flesh is Weak 퀘스트는 성직자?인 'Brother Janus' 한테 가서 끝내면 됩니다.

- Forgotten Lore는 위에서 말한 3번 시체 까지 가야되는데 가면 책한권 줍습니다. 킹스브릿지까지 가야 깰 수 있으므로 일단 먹었으면 창고에 박아 둡니다.

- 이 던전에서 꼭 얻어야할 아이템들이 몇 개 있습니다.

- 첫 번째는 위에서 말한 Ancient Tolassian Tome 책이고

- 두 번째는 다음 퀘스트인 고블린 킹 모가지 따러 갈때 필요한 화염 저항력을 올려주는 반지를 두개 얻도록 합니다.(나중에 클리어할 생각이라면 2개 까지는 필요없습니다.)

   그럼 고블린을 잡으면서 얻은 +10 화염 저항 신발과 +10 화염 저항 링 두개면 총 30저항이 되는데 이래도 잡기는 힘듭니다.

- 세 번째는 루비 입니다. 돌다보면 루비 한두개 쯤은 나올텐데 창고에 박아두세요. 나중에 퀘스트 깰때 필요합니다. 없으면 구하기 엄청 귀찮거든요

   

   

- 저도 3번 도전해서 잡았네요... 퀘스트 남기고 가면 찝찝해서 잡았습니다.

※ 팁 : 고블린 왕 잡으면 모가지 주는데 팔지 말고 꼭 보관 해두세요. 나중에 필요합니다.

         고블린 왕 모가지는 게임내에서 딱 한번만 얻을 수 있고 만약 팔았다 하더라도 다른 아이템으로 대처 가능하지만 그거 구하러 다니기가 여간 귀찮은게 아닙니다. 주변 몬스터들도 얄짤없이 강하구요

※ 팁 : 이 팁을 안적고 갈뻔 했네요.

         인벤토리를 보면 우측 하단 돈 왼쪽으로 'Quick slots'가 있습니다. 모든 아이템이 가능합니다. 제 경우에는 1, 2번에는 hp, mp 포션을 3번에는 스왑무기를 셋팅하고 다녔네요

※ 참고 : Ancient Verses

- 도데체 그놈의 고블린 머리랑 루비 등등은 어디다가 쓰는가 싶은가 궁금할까봐 가져왔습니다.

- Ancient Verses라는 퀘스트 인데

- 2 Rubies, 1 Merple, Head of Itharrak the Firedancer(고블린 왕 머리), 1 Damaged Wolf Pelt를 차례대로 쥐어줘야 합니다.

- 마지막으로 나이트 워커를 잡으면 'Sonnet' 이라는 유니크 템을 주는데 +2 Armor와 기본 3-8 데미지, +5 성령?? 데미지인데 공속도 12로 아주 좋습니다.(단, 워리어와 로그 전용입니다.)

다음편

Northern Bluemist River

- A Warrior's Honor : 워리어 용병과 유니크 반지를 얻을 수 있음

- Hunting bugs! : 벌래 퇴치

- A Wild Mystery : 벌래 퇴치 2

아이템 속성 설명

인터페이스나 스탯 스킬에 대해 알고 싶다면

참조 : 2017/12/22 - [일상다반사/게임] - [Exiled Kingdoms] 초반 공략 - 시작하면서

1. 시작 마을로 가기 전에

1) 시작과 함께 인터페이스에 대한 설명이 끝나면 'Adaon' 이라는 희대의 양아치 NPC를 만나게 됩니다.

   (나중에 대화 잘하면 반성하고 영원한 노예로 만들 수 있습니다.)

   (용병이 있는데 사실 어떻게 나눠야 할지 모르지만 돈주고 사는 용병과 NPC용병이 있습니다.

    돈주고 산 용병은 일회용입니다. 죽으면 ㅂ2

    NPC 용병은 플레이 하면서 3명 만났습니다.(각 직업별로) 죽어도 조금있으면 다시 되살아 나며 스킬도 쓰기 때문에 영원한 노예입니다.

    NPC 용병을 데리고 다니다가 나중에 다른 직업의 용병으로 바꿀 수도 있습니다.)

- 말걸기 싫지만 말을 걸어 봅니다.

- 이새퀴가 벌써부터 수작질을 부립니다. 별로 멀지도 않은 거리를 자꾸 자고 가자고 합니다.

  뭘 선택해도 자야합니다.

- 자고 일어나면 이렇게 빈 털털이가 됩니다.....

2. 시작마을, Lannegar(City)

- Lannegar Valley 맵에서 시작하고 첫 마을은 Lannegar 입니다.

1) 받을 수 있는 퀘스트 목록 및 설명

http://www.exiledkingdoms.com/wiki/index.php?title=Lannegar_(City)

ㄱ) 마을 내에서 받을 수 있는 퀘스트

- Goblin Hunt : 고블린 5마리 사냥

- Head Hunting : 고블린 왕 모가지 따기

- Gather ingredients : 꽃 모으기

- The Lost Explorer : 사라진 탐험가

- Flesh is Weak : 좀비가죽 3개 모으기

- The seed of trust : 보디가드

- Where is Giles : 이건 지금 받지도 못함....

ㄴ) 맵에서 받을 수 있는 퀘스트

- Forgatten Lore : 잃어버린 보물? 찾기

  (연계 퀘스트로 이거 깨면서 얻는 아이템들이 짭짤함)

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

ㄱ) Goblin Hunt

- 우선 마을입구의 'Captain Whitewater' 에게 가서 일자리를 달라고 떼쓰면 고블린 잡아오라고 합니다.

- 근처에서 고블린을 잡고 다시 가면 25골드와 hp 포션 하나를 받습니다.

- 퀘스트를 클리어 하면 다른 퀘스트(The Lost Explorer)를 받습니다.

- 받은 퀘스트는 상태창에서 'Journal' 에 보면 나옵니다.

ㄴ) The Lost Explorer

- The Lost Explorer 퀘스트를 보면 Lannegar의 서쪽 광산이 있답니다. 맵에서 보면 우측 그림처럼 왼쪽 위에 있는 던전입니다.

- 왼쪽 맵에서 좌측 중앙에 있는 방에 가면 오른쪽 그림처럼 감옥이 있습니다. 'Teram'에게 말을 걸면 열쇠는 모르겠고 레버가 있다고 합니다.

  레버는 왼쪽 맵에서 빨간색으로 표시된 곳에 있습니다. 당겨주고 다시 'Teram'에게 가서 따라오라고 하고 마을로 복귀하면 보상을 받습니다.

- 지금 굳이 맵을 다 돌지 않아도 조금만 있으면 지겹도록 돌테니 괜히 돌다가 임프한테 맞아 죽어서 저장 전으로 돌아가는 불상사가 발생하지 않았으면 좋겠습니다.

- 왼쪽은 레버 사진, 오른쪽은 레버를 당기고 다시 왔을 때 사진

- 'Teram'을 데려다 주고 'Captain' 에게 보상을 받으면서 처음에 물어봤던 도둑놈(Adaon)은 어디갔냐고 물어보니 킹스브릿지를 거쳐 뉴그랜드로 간다고 들었답니다.... 나중에 쫒아가야지요

ㄷ) Gather ingredients

- 마을에서 우측 상단에 있는 할아버지(Alchemist Markus) 한테 말을 걸면 'Blue Orched' 라는 꽃을 가져 오랍니다.

- 이렇게 생긴 꽃입니다.

- 지도에 표시된 위치에 파란색 꽃이 있으니 하나 가져다 주면 됩니다.

- 'Blue Orchid'를 가져다 주면 'Red Orchid'를 요구합니다. 그 이후에는 버섯 가져다 달라고 하는데 이건 다음 퀘스트를 깨면서 중간중간 줍도록합니다.

다음편

2017/12/25 - [분류 전체보기] - [Exiled Kingdoms] 공략 - Lannegar Valley, Lannegar(City) 2

- The seed of trust : 보디가드

- Head Hunting : 고블린 왕 모가지 따기