최적화
안되는 경우는 money의 최댓값인 10000을 넘는 것을 리턴할 때 -1을 출력하도록 했다. 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
using namespace std;
int table[10001];
int cache[10001];
bool visited[10001];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int n;
int go(int money) {
       //cout << money << endl;
       if (money == 0) {
              return cache[money];
       }
       if (money < 0) {
              return 10001;
       }
       int& ret = cache[money];
       if (ret != -1) {
              return ret;
       }
       cache[money] = INT32_MAX;
       for (int i = 0; i < n; ++i) {
              ret = min(ret, 1 + go(money - table[i]));
       }
       return ret;
}
int main(void) {
       memset(cache, -1, sizeof(cache));
       int money;
       cin >> n >> money;
       for (int i = 0; i < n; ++i) {
              cin >> table[i];
       }
       int ans = go(money);
       cout << (ans>10000 ? -1 : ans+1) << endl;;
       return 0;
}


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 14916 거스름돈  (0) 2018.04.02
[DP] 백준 9084 동전  (0) 2018.04.02
[DP] 백준 2011 암호코드  (0) 2018.01.02
[그래프] 백준 1987 알파벳  (0) 2017.12.14
[그래프] 백준 5567 결혼식  (0) 2017.12.13

boj.kr/2011

수가 아무것도 없을 때는 그 자체도 한가지 경우라고 볼 수 있으므로

=> d[0] = 1;

수가 1개 있을 때의 경우의 수는 1가지

d[1] = 1;

수가 2개 있을 때의 경우의 수는 

각자 하나씩의 알파벳을 나타내는 경우의 한가지와 

만약 두 숫자를 합쳐서 나타낼 수 있는 26 이하의 숫자라면 한가지가 더 추가되어 

한가지 또는 두가지가 된다. 

#include <iostream>
#include <string>
#define mod 1000000
using namespace std;
long long d[5001];
int main() {
       string s;
       cin >> s;
       int len = s.size();
       s = " " + s;
       d[0] = 1;
       for (int i = 1; i <= len; ++i) {
               int x = s[i] - '0';
               if (1 <= x && x <= 9) {
                      d[i] = (d[i] + d[i - 1]) % mod;
               }
               if (i == 1) continue;
               if (s[i - 1] == '0') continue;
               x = (s[i - 1] - '0') * 10 + (s[i] - '0');
               if (10 <= x && x <= 26) {
                      d[i] = (d[i] + d[i - 2]) % mod;
               }
       }
       cout << d[len];
       return 0;
}






저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 9084 동전  (0) 2018.04.02
[DP] 백준 동전 2 2294  (0) 2018.04.02
[그래프] 백준 1987 알파벳  (0) 2017.12.14
[그래프] 백준 5567 결혼식  (0) 2017.12.13
[EAZY] 백준 1065번 한수  (0) 2017.08.17

재귀 부분에서 dfs(nx,ny,cnt+1)을 

++cnt로 했는데 틀렸습니다 가 나왔다. 차이는 나중에 생각해 봐야겠다. 

새로 배운 것

1. 플러드 필에서 이동할 때 썼던 int dx,dy 배열을 한번에 2차원 배열로 사용하는 방법

2. 앞에것 을 방문했는지를 확인하는 데에 원래 배열을 만들어서 이전에 방문했던 지점을 

저장하고, for문을 이용해서 그 것을 매번 다음 nx,ny를 방문할 때마다 반복해야 했다. 

하지만 이 코드로 bool ch에 배열 number로 저장해서 한번에 찾을 수 있다는 걸 알았다. 

3. 백트래킹에 대해 아주 많이 생각해 보게 되었다. 



#include <iostream>
using namespace std;
int r, c;
char a[22][22];
bool ch[26];
int dd[][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
int ans = 0;
void dfs(int x, int y, int cnt) {
       if (cnt > ans) ans = cnt;
       for (int k = 0; k < 4; ++k) {
               int nx = x + dd[k][0];
               int ny = y + dd[k][1];
               if (0 <= nx&&nx < r && 0 <= ny&&ny < c) {
                      if (ch[a[nx][ny] - 'A'] == false) {
                              ch[a[nx][ny] - 'A'] = true;
                              dfs(nx, ny, cnt+1);
                              ch[a[nx][ny] - 'A'] = false;
                      }
               }
       }
}
int main() {
       cin >> r >> c;
       for (int i = 0; i < r; ++i) {
               cin >> a[i];
       }
       ch[a[0][0] - 'A'] = true;
       dfs(0, 0, 1);
       cout << ans;
       return 0;
       
}

저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 동전 2 2294  (0) 2018.04.02
[DP] 백준 2011 암호코드  (0) 2018.01.02
[그래프] 백준 5567 결혼식  (0) 2017.12.13
[EAZY] 백준 1065번 한수  (0) 2017.08.17
[EAZY] 백준 4673 셀프넘버  (0) 2017.08.15

boj.kr/5567

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.



풀이과정
첫번째 for : 양방향 그래프로 입력을 받는다. 
두번째 for : 1과 친구인 관계를 ch에 1로 저장하고 queue에 친구관계인 node를 push한다.
세번째 while : queue에 들어간 node를 하나씩 꺼내서 그 것과 연결된 노드 중 방문하지 않은 노드의 ch에 2를 저장한다.
마지막 for : ch가 1인 것과 2인 것의 개수를 센다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
queue<int> s;
vector<int> a[10001];
int ch[10001] = {0, };
int ans = 0;
int n;
int main() {
       cin >> n;
       int t;
       cin >> t;
       for (int i = 0; i < t; ++i) {
               int temp1, temp2;
               cin >> temp1 >> temp2;
               a[temp1].push_back(temp2);
               a[temp2].push_back(temp1);
       }
       int temlen = a[1].size();
       for (int i = 0; i < temlen; ++i) {
               ch[a[1][i]] = 1;
               s.push(a[1][i]);
       }
       while (!s.empty()) {
               int temp = s.front();
               s.pop();
               int len = a[temp].size();
               for (int j = 0; j<len; ++j)
                      if (ch[a[temp][j]] == 0) {
                              ch[a[temp][j]] = 2;
                      }
       }
       for (int i = 2; i <= n; ++i) {
               if (ch[i] == 2 || ch[i] == 1) {
                      ans++;
               }
       }
       cout << ans;
       return 0;
}


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 2011 암호코드  (0) 2018.01.02
[그래프] 백준 1987 알파벳  (0) 2017.12.14
[EAZY] 백준 1065번 한수  (0) 2017.08.17
[EAZY] 백준 4673 셀프넘버  (0) 2017.08.15
백준 C++ 11721번  (0) 2017.08.15 

#include<iostream>  

using namespace std;

int cal(int in);
int main(void){
	
	int in;
	
	cin >> in;
	
	int a = cal(in);
	
	cout << a << endl;
	
}

int cal(int in)
{
	int ans,in1,in2,in3;
	if(in<100)
		return in;
		
	ans = 99;
	
	for(int i=100;i<=in;++i)
	{
		in1 = i/100;
		in2 = (i-in1*100)/10;
		in3 = i%10;
		
		
		if((in1-in2)==(in2-in3))
			ans++;
	}
	
	return ans;
	
}


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[그래프] 백준 1987 알파벳  (0) 2017.12.14
[그래프] 백준 5567 결혼식  (0) 2017.12.13
[EAZY] 백준 4673 셀프넘버  (0) 2017.08.15
백준 C++ 11721번  (0) 2017.08.15
백준 C++ 11720번  (0) 2017.08.15 

#include<iostream>  

using namespace std;

int fun(int k);
int main(void)
{
	int forans[20000];
	for(int i=0;i<10000;++i)
	{
		forans[i] = i+1;
	}
	
	int a,k = 1;
	while(k!=10000){
		a=k;
		while(a<10000)
		{
			a=fun(a);
			forans[a-1] = -1;
			
		}
		k++;
	}
	
	for(int i=0;i<10000;++i)
		if(forans[i]!=-1)
			cout << forans[i] << endl;
    
    return 0;
}

int fun(int k)
{
	int a1=0,a2=0,a3=0,a4=0;
	if(k>=1000){
		a1 = k/1000;
		a2 = (k - a1 * 1000)/100;
		a3 = (k - a1 * 1000 - a2 * 100)/10;
		a4 = k%10;
	}
	else if(k>=100){
		a2 = k/100;
		a3 = (k - a2 * 100)/10;
		a4 = k%10;
	}
	else if(k>=10){
		a3 = k/10;
		a4 = k%10;
	}
	else{
		a4 = k;
	}
	
	int forreturn;
	
	forreturn = k+a1+a2+a3+a4;
	
	return forreturn;
	
	
}


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[그래프] 백준 5567 결혼식  (0) 2017.12.13
[EAZY] 백준 1065번 한수  (0) 2017.08.17
백준 C++ 11721번  (0) 2017.08.15
백준 C++ 11720번  (0) 2017.08.15
백준 C++ 11719번  (0) 2017.08.15 

#include <iostream>  
#include 

using namespace std;

int main(void)
{
	int l;
	char c[1000];
	cin >> c;
	for(l=0;l<100;++l)
	{
		if (c[l] == '\0')
			break;
	}
		
	
	for (int i = 0; i < l ; ++i)
	{
		cout << c[i];
		if ((i+1) % 10 == 0)
			cout << endl;
	}

}


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[EAZY] 백준 1065번 한수  (0) 2017.08.17
[EAZY] 백준 4673 셀프넘버  (0) 2017.08.15
백준 C++ 11720번  (0) 2017.08.15
백준 C++ 11719번  (0) 2017.08.15
백준 C++ 11718번  (0) 2017.08.15

<pre class="line-numbers"><code class="language-clike">

#include &lt;iostream&gt;  



using namespace std;


int main(void)

{

int n;

cin >> n;

char c[1000];

for (int i = 0; i < n; ++i)

cin >> c[i];


int sum = 0;

for (int i = 0; i < n; i++)

{

sum += (int)(c[i] - 48);

}

cout << sum;

}


 </code></pre><p><br /></p>


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[EAZY] 백준 4673 셀프넘버  (0) 2017.08.15
백준 C++ 11721번  (0) 2017.08.15
백준 C++ 11719번  (0) 2017.08.15
백준 C++ 11718번  (0) 2017.08.15
백준 C++ 10998번  (0) 2017.08.15 

#include <stdio.h>  
int main(){
	
	char str[101];
	
	while(gets(str) != '\0')
		puts(str);
}


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

백준 C++ 11721번  (0) 2017.08.15
백준 C++ 11720번  (0) 2017.08.15
백준 C++ 11718번  (0) 2017.08.15
백준 C++ 10998번  (0) 2017.08.15
백준 C++ 10871번  (0) 2017.08.15 

#include <iostream>  
#include 
using namespace std;
int main() {
    string word;
    while (1)
    {
        getline(cin, word);
        if (word == "")
            break;
        cout << word << '\n';
    }
}


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

백준 C++ 11720번  (0) 2017.08.15
백준 C++ 11719번  (0) 2017.08.15
백준 C++ 10998번  (0) 2017.08.15
백준 C++ 10871번  (0) 2017.08.15
백준 C++ 10869번  (0) 2017.08.15

+ Recent posts

티스토리툴바