acmicpc.net 11724(DFS), 1743(DFS), 11048(DP), 3067(DP)

https://www.acmicpc.net/problem/11724

파이썬으로 짰더니 시간초과가 났다.

#include <cstdio>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

int c = 0;
int visited[1001];
vector<int> graph[1001];

void dfs(int p)
{
	if(visited[p]==0)
		c++;
	else return;
	visited[p] = 1;
	stack<int> s;
	s.push(p);
	while(!s.empty())
	{
		int p = s.top(); s.pop();
		visited[p] = 1;
		for(int i=0;i<graph[p].size();i++)
		{
			if(visited[graph[p][i]]==0)
				s.push(graph[p][i]);
		}
	}
}

int main()
{
	int n,m;
	scanf("%d %d",&n, &m);
	for(int i=0;i<m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		graph[a-1].push_back(b-1);
		graph[b-1].push_back(a-1);
	}
	for(int i=0;i<n;i++)
		dfs(i);
	printf("%d\n",c);
	return 0;
}

https://www.acmicpc.net/problem/1743

역시 파이썬으로 시간초과가 났다.

#include <cstdio>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

int c = 0;
char trash[101][101];
int ty[]={1,0,-1,0};
int tx[]={0,-1,0,1};
int n,m,k;
void dfs(int y,int x)
{
	int visited[101][101]={0,};
	int count = 0;
	visited[y][x] = 1;
	stack<pair<int, int>> s;
	s.push(make_pair(y,x));
	while(!s.empty())
	{
		int py = s.top().first; 
		int px = s.top().second;
		s.pop();
		count += 1;
		for(int i=0;i<4;i++)
		{
			int y = py + ty[i];
			int x = px + tx[i];
			if(y>n-1 || x>m-1 || x<0 || y<0)
				continue;
			if(visited[y][x]==0 && trash[y][x]=='#')
			{
				s.push(make_pair(y,x));
				visited[y][x] = 1;
			}
		}
	}
	if(count > c)
		c = count;
}

int main()
{
	scanf("%d %d %d",&n, &m, &k);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			trash[i][j] = '.';
	for(int i=0;i<k;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		trash[a-1][b-1] = '#';
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(trash[i][j]=='#')
				dfs(i,j);
	printf("%d\n",c);
	return 0;
}

https://www.acmicpc.net/problem/11048

쉬운 DP문제.

# -*- encoding: cp949 -*-
n,m=map(int,raw_input().split())
arr = [map(int,raw_input().split())for i in xrange(n)]
dp = [[0 for i in xrange(m)]for i in xrange(n)]
dp[0] = arr[0]
for i in xrange(1,m):
    dp[0][i] = dp[0][i-1] + arr[0][i]
for i in xrange(1,n):
    dp[i][0] = dp[i-1][0] + arr[i][0]
    for j in xrange(1,m):
        dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + arr[i][j]
print dp[n-1][m-1]

https://www.acmicpc.net/problem/3067

# -*- encoding: cp949 -*-
for t in xrange(input()):
    n=input()
    dp = [0 for i in xrange(10002)]
    c=map(int,raw_input().split())
    m=input()
    dp[0] = 1
    for i in xrange(n):
        for j in xrange(c[i],m+1):
            dp[j] += dp[j-c[i]]
    print dp[m]