문제링크: www.acmicpc.net/problem/2629

반례를 못찾아서 고생한 문제입니다.

양팔저울을 통해서 구슬의 무게를 잴 수있는지 확인하는 문제입니다. 모든 경우를 확인해주어야 합니다.

근데 이때 재귀를 사용하여 해결할 수 있고 dp를 활용하자는 생각을 가지는 것이 문제 접근의 핵심입니다.

첫 번째, dp구현하기

dp[i][j]는 i는 현재 무게, j는 탐색하는 추의 인덱스 입니다.

두 번째, 재귀 점화식 도출

모든 경우를 다 고려해야 합니다. 즉, 

ret = solved(abs(weight - sinker[i]), i + 1);
ret = max(ret, solved(weight, i + 1));
ret = max(ret, solved(weight + sinker[i], i + 1));

3가지를 고려해야 합니다.

이때 abs(weight - sinker[i]) 부분 때문에  고생했습니다.

저는 처음에 

if (sinker[i] <= weight) {
ret = solved(weight - sinker[i], i + 1);
}

이렇게 구현했습니다. 근데 이때 추보다 작은 무게가 먼저 들어올때 추를 사용하지 않고 넘어가다보니 오류가 났습니다.

해결하기위해서 2가지 방법이 있습니다.

1. 인덱스를 사용하기 

2. 그냥 절대값으로 해결하기

저는 2번을 선택했습니다. 절대값으로 고려하여도 저울의 어느쪽에 두는지의 차이이기 때문에 상관이 없습니다.

아래는 정답코드입니다.

코드를 천천히 따라가면서 이해해보세요

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int a = 0, b = 0;
int sinker[31] = { 0, };
int arr[7] = { 0, };
int dp[100001][31];


int solved(int weight, int current) {
	if (weight == 0)
		return 1;
	if (current > a)
		return 0;

	int &ret = dp[weight][current];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = current; i <= a; i++) {

		ret = solved(abs(weight - sinker[i]), i + 1);
		ret = max(ret, solved(weight, i + 1));
		ret = max(ret, solved(weight + sinker[i], i + 1));
		return ret;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> a;
	for (int i = 1; i <= a; i++)
		cin >> sinker[i];

	cin >> b;
	for (int i = 1; i <= b; i++) {
		int temp;
		cin >> temp;
		memset(dp, -1, sizeof(dp));

		
		if (solved(temp, 1))
			cout << 'Y';
		else
			cout << 'N';

		if (i != b)
			cout << ' ';
	}
	cout << endl;
	return 0;

}

문제링크:www.acmicpc.net/problem/4811

우선 규칙성을 찾으려고 노력했습니다. 그런데 규칙을 못찾았고, 자연스레 재귀함수를 사용한 dp인 up-down 방식으로 생각했습니다.

문제에서 주어지는 조건처럼 전체 알약, 반쪽 짜리 알약으로 구분하여 

dp[i][j]은 하나짜리 알약 i개가 있고 반쪽 짜리 알약 j개가 있을때 최대 경우의 수를 나타냅니다.

아래는 재귀함수 코드입니다.

long long solved(int whole, int half) {
	if (whole == 0)
		return 1;
	long long &ret = dp[whole][half];
	if (ret != -1)
		return ret;

	ret = solved(whole - 1, half + 1);

	if (half > 0)
		ret += solved(whole, half - 1);


	return ret;
}

만약 whole =0 이면 half만 남은 상태니까 결과값은 1!

그리고 모든 경우에서 whole -1 , half +1  호출

만약 half가 있다면 whole,half-1도 호출후 더하기

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
using namespace std;


long long dp[31][31];

long long solved(int whole, int half) {
	if (whole == 0)
		return 1;
	long long &ret = dp[whole][half];
	if (ret != -1)
		return ret;

	ret = solved(whole - 1, half + 1);

	if (half > 0)
		ret += solved(whole, half - 1);


	return ret;
}
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	
	for (int i = 1; i <= 1001; i++) {
		memset(dp, -1, sizeof(dp));
		int temp;
		cin >> temp;
		if (temp == 0)
			break;
		cout << solved(temp, 0) << "\n";
	}

	return 0;
}

1등 취업카페 독취사 링크입니다.

링크: cafe.naver.com/dokchi?iframe_url_utf8=%2FArticleRead.nhn%3Fclubid%3D16996348%26articleid%3D485362

꼭 취업 성공하세요.

일본 최고 방송국인 NHK에서 공개한 역대 베스트 일본 애니 그중에서 TOP10을 뽑도록 하겠습니다.

출처:www6.nhk.or.jp/anime/

곧장 1위부터~

1위

타이거 앤 버니

타이거 앤 버니는 2011년 4월부터 방영된 일본의 애니메이션이다.

45년 전부터 나타난 초능력자들인 N.E.X.T.가 히어로가 되고, 그런 히어로가 작중 기업의 스폰서를 받아서 활동하며, 그 활약을 중계하는 방송 프로그램, 그 방송의 시청률에만 혈안이 된 방송국, 또한 활약을 통한 순위 경쟁 등의 자극적인 요소가 많다.

2위

마법소녀 마도카☆마기카

조금 소심하고 우물쭈물거리는 평범한 소녀 카나메 마도카는 어느 날 수수께끼의 큐트한 생물 큐베를 만나서 '마법소녀가 되어 달라'는 부탁을 받게 된다.
그리고 마도카는 어른스럽고 믿음직한 선배 토모에 마미, 밝고 명랑한 친구 미키 사야카, 쿨시크한 전학생 아케미 호무라와 우정을 나누고 함께 마을을 지켜나가면서 성장해 간다.

3위

러브 라이브

니코니코니~

프로젝트의 요점은 스쿨 아이돌 캐릭터를 주역으로 여러 가지 관련 활동을 전개하는 것이다. 중심이 되는 스쿨 아이돌 그룹은 총 3개의 그룹으로, μ’s(뮤즈), Aqours(아쿠아), 그리고 니지가사키 학원 스쿨 아이돌 동호회이다. 애니메이션 원작으로 잘못 알려지기도 했지만 사실 음반으로 시작된 프로젝트이며, 애니메이션 외에도 잡지연재, 코믹스, 소설 등 세부 설정이 조금씩 다른 다양한 미디어믹스로 구성되어 있다.
러브 라이브!의 캐릭터를 담당하는 성우들이 같은 명의로 관련 라이브나 행사를 소화한다는 점이 특징이다.

4위

코드기어스: 반역의 를르슈

무대는 근대의 정치 + 현대의 사회 + 미래의 과학력이 적당히 섞인 세계. 세계 제일의 초강대국 신성 브리타니아 제국은 이 세계에서 가장 귀중한 자원인 사쿠라다이트를 노리고 일본을 침공, 폭풍 항복을 받아내고 식민지로 삼는다. 브리타니아 총독의 지배를 받게 된 일본은 국가이름을 박탈당하고『Area 11』으로 명명, 국민들은『일레븐』이라고 불리며 폭정과 차별에 시달린다.

그로부터 7년 후, 브리타니아의 제11황자인 소년 를르슈 람페르지는 어머니가 암살당하고 그 충격으로 불구가 된 동생 나나리와 함께 일본으로 쫓겨나게 되어 신분을 숨기고 평범한 학생으로 생활하고 있었다. 브리타니아에 강렬한 원한을 품고 있는 를르슈는 우연히 C.C.라는 의문의 소녀를 만나 기아스라는 초자연적인 힘을 얻게 되고, 가면으로 정체를 숨긴 후 제로라고 스스로 칭하며 반 브리타니아 레지스탕스를 수하로 끌어들여 복수에 나선다.

5위

카드캡터 체리

평범한 초등학교 4학년 키노모토 사쿠라는 고고학자인 아빠의 서고에서 낡은 책을 우연히 펼쳤다가 봉인의 수호자 케르베로스를 깨우고 만다.

케르베로스로부터 마법의 힘을 받아 카드캡터가 된 사쿠라는 이 세상에 재앙을 가져온다는 크로우 카드의 회수와 봉인을 명받는다. 사쿠라는 마을에 일어나는 이상한 일들을 하나하나 해결하며 카드를 봉인한다.

그러던 어느 날 사쿠라의 반에 새로운 남학생이 전학을 온다. 그 전학생은 다짜고짜 사쿠라에게 크로우 카드를 내놓으라고 하는데?!

6위

오소마츠 상

마츠노 家에는 똑같이 생겼지만 똑같이 생긴 게 아닌 6쌍둥이 오소마츠, 카라마츠, 쵸로마츠, 이치마츠, 쥬시마츠, 토도마츠가 살고 있다. 6쌍둥이는 얼굴은 똑같지만 개성만점의 다양한 성격을 자랑한다. 일정한 직업 없이 빈둥거리며 하루하루를 보내는 6쌍둥이지만 독특한 여섯 명이 모인 만큼 사건사고가 끊이지 않으며 시끌벅적한 일상이 펼쳐진다.

여기에 이들만큼이나 존재감이 넘치는 캐릭터인 아이돌(?) 토토코, 시건방진 치비타, 말끝마다 "다용"을 붙이는 다용, 자칭 프랑스에서 살다온 이야미, 팬티 한 장 차림의 데카판, 깃발을 꽂고 있는 하타보 등이 가세해서 끊임없이 요절복통 에피소드들이 이어진다.

7위

은혼

카부키쵸라는 환락가를 주 무대로 하고 있으며 패전한 전쟁영웅, 몰락한 사무라이, 밀항한 가출 소녀, 불량 경찰, 술집 여자, 인신 매매 당한 유녀, 노숙자, 야쿠자, 오카마 등 사회에서 멸시 받고 소외 당하는 인물들을 주조연으로 내세운다. 한마디로 등장인물들의 인생이 하나같이 막장이다. 막장이기만 하면 차라리 다행인데 정신줄도 놓았다. 정상적으로 보이는 인물들도 잘 보면 어딘가 어긋나있다. 밑에는 언제나 더 밑바닥이 있다는 걸 아주 잘 보여주는 인간들. 그런데 진지할 때는 이상하게 매우 강하고 멋있어진다. 이런 인간 군상들이 독자에게 웃음과 감동을 준다.

8위

조커 게임

세계 대전의 불씨가 되살아난 쇼와 12년(1937년) 가을, 제국 육군의 유키 중령에 의해 스파이 양성 부문 'D 기관'이 극비리에 설립된다.

본토 출신의 군인을 존중하는 육군의 풍조에 반하여 기관원으로 뽑힌 것은 도쿄와 교토에 있는 일반 대학을 졸업하고 초인적인 선발 시험을 아무렇지 않게 거친 젊은이들이었다.

그들은 마술사 같은 지략을 가진 유키 중령에게 폭약과 무전 조작법, 자동차와 비행기 조종법은 물론이고 소매치기, 금고털이 기술에 이르기까지 스파이 활동에 필요한 온갖 기술을 익히고 임지(任地)로 떠난다.

「죽지 마라, 죽이지 마라」

눈에 띄지 않는 것을 중시하는 스파이에게 자결과 살인은 최악의 선택지라는 D 기관은 육군 중심부로부터 심한 반발을 받아도 아군을 속이고 적의 의표를 찔러 세계 속을 암약한다.

9위

은하영웅 전설

머나먼 미래... 한 사람이 이제는 기억 속에 가물가물한 옛 이야기를 회상하며 이야기를 시작한다.

이야기는 작중 시대로부터 기억 속에 잊혀진 엄청나게 오래 전의 과거이다. 강철 인간 루돌프 대제가 골덴바움 왕조의 은하제국을 세운 지 500년이 지났다. 어느덧 황혼에 접어든 제국... 이 황혼기에 등장한 젊은 장군 라인하르트는 빼어난 미모와 천재적인 두뇌, 누이를 앗아간 골덴바움 왕조와 그에 빌붙은 귀족들에 대한 사무친 적개심을 바탕으로 은하계 지존의 자리를 향해 무섭게 달려간다.

그에 맞서는 공화파, 자유행성동맹의 유일한 희망인 젊은 장군 양 웬리. 그는 빈껍데기뿐인 유산과 자유로운 영혼을 남긴 채 아버지가 죽은 후 공짜로 역사 공부를 하기 위해 사관학교를 지망한다. 그러나 운명의 수레바퀴는 그를 전쟁의 신으로 만들 뿐, 결코 역사학자로 만들어 주지 않는다.

야망과 음모, 배신의 정글을 헤치고 저마다의 목표를 향해 달리는 영웅들 앞에 한치도 양보할 수 없는 격돌의 순간은 시시각각 다가오는데.....

10위

주문은 토끼입니까?

래빗 하우스에서 먹고 자고 일하는, 밝고 명랑하고 살짝 허당인 코코아.

그곳 사장님의 손녀딸로, 말투는 공손(?)하지만 태도는 더없이 쿨~한 치노.

부잣집 아가씨이건만 어쩐지 군인의 향기를 풍기는 또 다른 알바생 리제.

코코아의 학교 친구이자 나긋나긋한 전통찻집 아가씨인 치야.

카페인에 취하는 특이체질을 가진 허브티 카페 알바생인 가난 소녀 샤로.

그리고 정체를 숨기고 있는 수상한 토끼 티피.

사랑스러운 친구들이 그려가는 카페스러운 일상♥

지금까지 일본 인기 애니 TOP10을 알아봤습니다.

정보가 유익하셨다면 광고 한번씩 눌러주세요!

글과 그림의 출처는 나무위키입니다.

namu.wiki/w/%EB%82%98%EB%AC%B4%EC%9C%84%ED%82%A4:%EB%8C%80%EB%AC%B8

문제링크:www.acmicpc.net/problem/2533

어려웠습니다..ㅠㅠ

dp(up-down) 문제인건 인식했지만 우선 그래프를 어떤식으로 구현하고 dp를 구현할지 설계를 하는데 어려움을 겪었습니다.

• 1. 단방향 그래프 만들기
• 2. 그래프를 탐색하며 최소수 구하기

1. 우선 입력 받을때는 양방향으로 받고 재귀함수를 통해서 결과를 도출합니다.

void make_graph(int current, int parent) {
	if (parent != 0) {
		graph[parent].push_back(current);
	}
	
	for (int i = 0; i < vec[current].size(); i++) {
		if (parent == vec[current][i]) continue;
		make_graph(vec[current][i], current);
	}

}

parent 벡터에만 child 노드들을 넣어 놓음으로서 단방향 트리를 구현했습니다.

2. 그래프를 탐색하며 최소수 구하기는 일반적인 dp(up-down)과 흡사합니다. 

if (adapter) {
		ret = 1;
		for (int i = 0; i < graph[current].size(); i++)
			ret += min(solved(graph[current][i], adapter), solved(graph[current][i], !adapter));
	}
	else {
		ret = 0;
		for (int i = 0; i < graph[current].size(); i++)
			ret += solved(graph[current][i], !adapter);
	}

 1) 현재 노드가  얼리 어뎁터일때는 자식노드가  얼리 어뎁터일수도, 아닐수도 있습니다.

 2) 하지만 현재 노드가 얼리어뎁터가 아니라면  무조건 다음 노드는 얼리 어뎁터이어야 합니다.

2가지 조건을 통해서 재귀를 구현했습니다. 

아래는 정답코드입니다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;


int n = 0;
vector <int> vec[1000001];
vector <int> graph[1000001];
int dp[1000001][2] = { 0, };

int solved(int current, bool adapter) {
	if (graph[current].empty()) {
		if (adapter)
			return 1;
		else
			return 0;
	}
	
	int &ret = dp[current][adapter];
	if (ret != -1)
		return ret;

	if (adapter) {
		ret = 1;
		for (int i = 0; i < graph[current].size(); i++)
			ret += min(solved(graph[current][i], adapter), solved(graph[current][i], !adapter));
	}
	else {
		ret = 0;
		for (int i = 0; i < graph[current].size(); i++)
			ret += solved(graph[current][i], !adapter);
	}

	return ret;

}

void make_graph(int current, int parent) {
	if (parent != 0) {
		graph[parent].push_back(current);
	}
	
	for (int i = 0; i < vec[current].size(); i++) {
		if (parent == vec[current][i]) continue;
		make_graph(vec[current][i], current);
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n -1 ; i++) {
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	make_graph(1, 0);
	/*
	for (int i = 0; i < n; i++) {
		cout << graph[i].size() << endl;
	}*/

	memset(dp, -1, sizeof(dp));
	cout << min(solved(1, 0), solved(1, 1)) << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/18427

무난한 난이도의 dp 문제였습니다.

한 학생당 최대 1개의 블록라는 조건을 통해서 배낭문제 알고리즘으로 해결할 수 있습니다.

dp[i][j] 는 i번째까지 학생에게 j높이에서의 최대 경우의수라고 할때, 아래와 같이 됩니다. (초기화 작업으로 0일때는 1로 지정)

첫번째 학생이 2,3,5니까, dp[1]은 101101이 되고 두번째 학생을 포함하면 101203이되고... 

그러면 학생이 가진 블록뺀 dp[i-1][j-vec[i][k]] 만큼씩 더해주고 그 이후에 dp[i-1][j] 을 더해주면 해결됩니다.

조심할 점은  if (j >= vec[i][k]) 일때 dp[i - 1][j - vec[i][k]]을 수행하여야 한다는 점이다. 

아래는 정답코드입니다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int n, m, h;
vector <int> vec[51];
int dp[51][1001] = { 0, };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> h;
	cin.ignore(1);

	for (int i = 1; i <= n; i++) {
		string temp;
		getline(cin, temp, '\n');
		
		for(int j=0;j<temp.size();j++)
			if(temp[j]==' '||j==0)
				vec[i].push_back(stoi(&temp[j]));

			
	}
	

	
	//solve

	for (int i = 0; i <= n; i++)
		dp[i][0] = 1;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= h; j++) {
			
			
			for (int k = 0; k < vec[i].size(); k++) {
				
				if (j >= vec[i][k]) {
					dp[i][j] += dp[i - 1][j - vec[i][k]];
					dp[i][j] %= 10007;
				}
			}		
			dp[i][j] += dp[i - 1][j];
			dp[i][j] %= 10007;
		}
	}


	cout << dp[n][h] << endl;


	return 0;
}

문제링크:www.acmicpc.net/problem/2839

레전드 문제 설탕배달입니다....ㅋㅋㅋ

입문자분들이 가장 많이 풀고 절망을 느끼는 문제입니다.

오랜만에 다시 풀어봤는데 감회가 새로워서 포스팅합니다.

저의 예전 답입니다.

#include <stdio.h>
int main()
{
	int x = 0, y = 0, N = 0, resultx = 0, resulty = 0;
	int i = 0;
	int j = 0;
	scanf("%d", &N);
	for (x = 0; i <= N; x++)
	{
		i = 5 * x;
		for (y = 0; j <= N; y++)
		{
			j = 3 * y;
			if (i + j == N)
			{
				resultx = x;
				resulty = y;
			}
		}
		j = 0;
	}
	if (resultx == 0 && resulty == 0)
		printf("%d\n", -1);
	else
		printf("%d\n", resultx + resulty);
}

이중포문을 사용해서 구현했습니다.

5씩 증가하는 i와 3씩 증가하는 j의 모든 조합을 비교해보며 결과값을 도출하는 방법입니다. i가 j보다 상위 반복문에 있기 때문에 i가 최대가 되는 결과값이 최종적으로 resulty, x 에 저장이 되어지고 이를 통해 결과값을 얻습니다.

하지만 만약에 시간이나 데이터 크기가 더욱 커진다면 테스트를 통과하지 못할 확률이 있습니다.

예를 들어서 n=1000,000라면 해당 코드는 O(n^2)이므로 시간제한 1초를 훌쩍 넘게 됩니다.

이를 예방하기 위해서  반복문 하나만 써서 해결하는 방식도 생각해봤습니다.

	int answer = 0;
	int mod, num, result;
	num = n / 5;



	while (num >= 0) {

		mod = 0;
		result = 0;

		if (num > 0) {
			mod = n - 5 * num;
			result = num;
		}
		else {
			mod = n;
		}

		result += mod / 3;
		mod = mod % 3;

		if (mod == 0) {
			answer = result;
			return answer;
		}

		num--;

	}
	if (mod != 0)
		return -1;

	
		
	//return answer;

사실 같은 원리입니다. while문에서 5로 나눌수 있는 만큼 반복하며 진행합니다. 이때 5로 나눈 나머지만큼 3으로 다시한번 나눠보고 나머지가 0된다면 그대로 바로 결과를 출력하는 구조입니다.

사실은 2중포문을 사용할 필요가 없던 코드입니다. 

사실 구현하면서 고민을 꽤 많이 했던터라 아직도 많이 부족하다는 것을 느낄 수 있었습니다. 

더욱 열심히 해서 알고리즘 마스터가 되겠습니다. 

문제링크: www.acmicpc.net/problem/2616

down-up방식 점화식을 구하지 못해 up-down 방식을 사용했습니다.

한점 기준으로 해당 위치부터 소형 기관차를 사용하는 경우 혹은 사용하지 않는 경우 두가지를 비교해주며 결과값을 도출했습니다.

dp[i][j]는 i번째 위치에서부터  j개의 소형기관차를 사용할때 얻을 수 있는 최대값을 가르킵니다. 이때 점화식은

• max(solved(current + 1, cnt), solved(current + k, cnt + 1) + (arr[current + k - 1] - arr[current - 1])); 

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n = 0, k = 0;
int dp[50001][3] = { 0, };
int arr[50001] = { 0, };

int solved(int current, int cnt) {

	if (current > n || cnt == 3)
		return 0;

	int &ret = dp[current][cnt];
	if (ret != -1)
		return ret;

	if ((current + k - 1) <= n)
		ret = max(solved(current + 1, cnt), solved(current + k, cnt + 1) + (arr[current + k - 1] - arr[current - 1]));


	return ret;
}



int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int temp = 0;
		cin >> temp;
		arr[i] = arr[i - 1] + temp;
	}
	cin >> k;
	memset(dp, -1, sizeof(dp));
	cout << solved(1, 0) << endl;

	/*
	for (int i = 1; i <= n; i++)
		cout << arr[i] << endl;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++)
			cout << dp[i][j] << ' ';
		cout << endl;
	}*/
	return 0;
}

down-up방식도 가능할거 같아 찾아봤습니다.

lyzqm.blogspot.com/2017/03/2616.html

DP[N][M]=max(DP[N][M−1],DP[N−1][M−K]+S[M]−S[M−K] 해당 점화식 사용하셔서 푸는 답도 있습니다.