Be myself :: 'Algorithm' 카테고리의 글 목록

달력

32024  이전 다음

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

그냥 마음놓고 아무생각없이 backtracking으로 짰다가 시간초과를 맞은 문제.

처음엔 한 row마다 전부 A혹은 B로 바꾸는데 배열을 순회하며 O(W)의 시간이 걸리도록 짰지만.. 이를 더 빠르게 처리할 방법을 생각하다 포기했다가.. 알고리즘 관련 책을 뒤져보니 backtracking시 시간초과가 난다면 bitmasking을 이용하면 될 수도 있다는 문구를 보고 곰곰히 생각해봤다.

한 row를 bit로 표현하면 A, B로 바꿀때 O(1)로 줄일수 있다!!

이를 이용해 문제를 다시 풀었고 AC를 받아냄..ㅠㅠ 전체 시간은 O(w*d*3^d)

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

#define INF 2e8
using namespace std;
int D, W, K;
int CheckArr[21];
bool Check();
int Count[1 << 13];
int solve(int row);
int main()
{
	int T;
	scanf("%d", &T);

	//bit counting
	for (int i = 0; i < (1 << 13); i++)
	{
		int z = i;
		int maxS = 0;
		int sum = 0;
		while (z != 0)
		{
			if ((z & 1) == 1)
			{
				sum += 1;
			}
			else
			{
				maxS = max(maxS, sum);
				sum = 0;
			}
			z /= 2;
		}
		maxS = max(maxS, sum);
		Count[i] = maxS;
	}

	for (int t = 1; t <= T; t++)
	{
		int ans = 0;
		memset(CheckArr, 0, sizeof(int) * 21);
		scanf("%d %d %d", &D, &W, &K);
		for (int i = 1; i <= D; i++)
		{
			for (int j = 1; j <= W; j++)
			{
				int tmp;
				scanf("%d", &tmp);
				if(tmp != 0)
					CheckArr[i] |= (1<<(W-j));
			}
		}
		
		ans = solve(1);
		printf("#%d %d\n", t, ans);
	}
	return 0;
}

int solve(int row)
{
	//기저조건 다 칠했을 때
	if (row == D + 1)
	{
		if (Check())
			return 0;
		else
			return INF;
	}

	//안칠하는 경우
	if (Check())
		return 0;
	int ans = INF;
	ans = min(ans, solve(row + 1));

	//case1 A로 바꾸는 경우
	int origin = CheckArr[row];
	CheckArr[row] = 0;
	ans = min(ans, solve(row + 1) + 1);
	CheckArr[row] = origin;

	//case2 B로 바꾸는 경우
	CheckArr[row] |= ((1 << W)-1);
	ans = min(ans, solve(row + 1) + 1);
	CheckArr[row] = origin;
	
	return ans;
}

bool Check()
{
	bool check = true;
	bool checkA = true;
	bool checkB = true;
	for (int k = 1; k <= W; k++)
	{
		int tmp = 0;
		checkA = true;
		checkB = true;
		for (int r = 1; r <= D; r++)
		{
			int current = (CheckArr[r] >> (k - 1)) & 1;
			tmp |= (current << (r-1));
		}
		
		if (Count[tmp] < K)
			checkA = false;
		
		int tmp2 = (~tmp) & ((1 << D) - 1);
		if (Count[tmp2] < K)
			checkB = false;

		if (!checkA && !checkB)
		{
			check = false;
			break;
		}
	}
	
	return check;
}

 

'Algorithm' 카테고리의 다른 글

[baekjoon 1500]최대 곱  (0) 2017.09.28
[baekjoon 11057]오르막 수  (0) 2017.08.12
[baekjoon 11727] 2*n타일링2  (0) 2017.08.11
[algospot]Synchronizing Clocks  (0) 2016.01.28
[Algospot]PICNIC  (0) 2016.01.07
Posted by flack3r
|

dp로 푼사람이 아무도 없어서 올려본다.

점화식을 세우면 다음과 같다

dp[s][k] = max(dp[s-X][k-1] * X) (1 <= X <= S-1)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int S, K;
	scanf("%d %d", &S, &K);
	vector<vector<long long>> dp(S + 1, vector<long long>(K + 1));
	for (int i = 1; i <= S; i++)
	{
		dp[i][1] = i;
	}

	for (int k = 2; k <= K; k++)
	{
		for (int s = 1; s <= S; s++)
		{
			for (int x = 1; x <= s - 1; x++)
			{
				dp[s][k] = max(dp[s][k], dp[s - x][k - 1] * x);
			}
		}
	}

	printf("%lld\n", dp[S][K]);
}


'Algorithm' 카테고리의 다른 글

[sw expert]모의sw역량테스트 보호필름  (1) 2017.10.09
[baekjoon 11057]오르막 수  (0) 2017.08.12
[baekjoon 11727] 2*n타일링2  (0) 2017.08.11
[algospot]Synchronizing Clocks  (0) 2016.01.28
[Algospot]PICNIC  (0) 2016.01.07
Posted by flack3r
|

간단한 dp문제이다. 길이가 N일떄 마지막 숫자를 하나의 상태로 두고 이차원 배열로 만들어서 상태dp로 풀어준다. 그래서 결과 값은 dp[N][i] (i는 0~9까지)값을 모두 더한 값이 되겠다.

코드도 단순하다.


#include <stdio.h>
#include <iostream>
using namespace std;

int dp[1001][10];
int main()
{
	int N;
	int ans = 0;
	scanf("%d", &N);
	dp[1][0] = 1;
	for (int i = 1; i <= 9; i++)
	{
		dp[1][i] = 1;
	}
	
	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			for (int k = j; k >= 0; k--)
			{
				dp[i][j] +=  (dp[i-1][k]) % 10007;
			}
		}
	}
	
	for (int i = 0; i <= 9; i++)
	{
		ans += (dp[N][i]) % 10007;
	}
	printf("%d\n", ans % 10007);
	return 0;
}

'Algorithm' 카테고리의 다른 글

[sw expert]모의sw역량테스트 보호필름  (1) 2017.10.09
[baekjoon 1500]최대 곱  (0) 2017.09.28
[baekjoon 11727] 2*n타일링2  (0) 2017.08.11
[algospot]Synchronizing Clocks  (0) 2016.01.28
[Algospot]PICNIC  (0) 2016.01.07
Posted by flack3r
|

간단하게 상태dp로 풀어줍니다.

n일 때, 하나의 칸의 상태는 총 4가지 입니다.  1) 비어있는 경우 , 2) 위에 칸이 채워진 경우 3) 아래 칸이 채워진 경우 4) 모두 채워진 경우

규칙을 찾으면 다음과 같습니다. (n일떄 n-1은 모두 채워야 합니다. 왜냐하면 사용 가능한 타일이 2*1, 2*2 뿐이기 때문에 n-1을 모두 채우지 않으면 n+1에서 채울 수가 없습니다.)

위와 같이 규칙을 찾을 수 있습니다. 위를 토대로 코드를 짜면 다음과 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int dp[1001][4] = { 0, };
int main()
{
	int N;
	scanf("%d", &N);
	dp[1][0] = 1;
	dp[1][1] = 1;
	dp[1][2] = 1;
	dp[1][3] = 1;
	
	for (int i = 2; i <= N; i++)
	{
		dp[i][0] = dp[i - 1][3] % 10007;
		dp[i][1] = dp[i - 1][2] % 10007;
		dp[i][2] = dp[i - 1][1] % 10007;
		dp[i][3] = ((dp[i - 1][0] * 2) % 10007 + dp[i - 1][3]) % 10007;
	}

	printf("%d\n", dp[N][3] % 10007);
	return 0;
}

'Algorithm' 카테고리의 다른 글

[sw expert]모의sw역량테스트 보호필름  (1) 2017.10.09
[baekjoon 1500]최대 곱  (0) 2017.09.28
[baekjoon 11057]오르막 수  (0) 2017.08.12
[algospot]Synchronizing Clocks  (0) 2016.01.28
[Algospot]PICNIC  (0) 2016.01.07
Posted by flack3r
|

[algospot]Synchronizing Clocks

2016. 1. 28. 16:51

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

[Algospot]PICNIC

2016. 1. 7. 11:09

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.