Algorithm

Codeforces Round 377 (Div. 2)

알고리즘

처음으로 참가해본 코드포스 라운드다. 밤 11시 넘어서 시작하니 군대 안에 있을때는 참가하고 싶어도 할 수가 없었는데 말출 나와서 처음으로 참가해봤다.

시간을 잘 못 알아서 20분정도 늦게 시작했고 두 문제밖에 못 풀었다 ㅠㅠ. 조금 더 일찍 시작했으면 세문제 까지 풀 수 있었을것 같은데..

최근에 휴가를 많이 나오다보니 조금 나태해진것 같은데 이번에 라운드 참가하고나니 의욕이 다시 생겼다.


풀이

A. Buy A Shovel

http://codeforces.com/contest/732/problem/A

삽을 사야한다. 삽의 가격이 k원일때, 10원 동전이 무한개를 사용할 수 있고 r원 동전이 단 하나 있을때 거스름돈 없이 삽을 살 수 있는 최수 갯수를 구하는 문제이다. 약간 함정이 있는게 거스름돈 없이 사면 된다는 것이 함정이다. r원 동전이 하나밖에 없기 때문에 처음에 r원을 무조건 사용해야 한다는 생각을 했었는데 WA가 나와서 다시 보니 그냥 거스름돈을 남기지 않으면 되는거였다. 매우 쉬운 문제였다.

#include <stdio.h>
int main(){
	int k,r,m=1;
	scanf("%d%d",&k,&r);
	while(1){
		int price = k*m;
		if(price % 10 == 0 || price % 10 == r)
			break;
		m++;
	}
	printf("%d",m);
}


B. Cormen — The Best Friend Of a Man

http://codeforces.com/contest/732/problem/B

개를 산책시키기 위한 계획을 짜야한다. n일동안의 계획이 주어졌을때 강아지를 이틀 연속으로 최소 k번 산책을 시켜야 한다. 첫번째 예제를 보면 n=3, k=5이고 1일부터 3일까지 각각 {2, 0, 1}번 산책을 하려고 하는데 이 계획은 이틀 연속으로 최소 5번 산책을 시키지 않으므로 산책을 더 시켜야한다.여기서 보면 알겠지만 이 문제는 스페셜 저지 문제이다. 연속되는 이틀간 최소 5번 산책을 시키려면 4번 더 산책을 가야하는데 이 때 {2, 3, 2}와 {2, 4, 1} 둘 다 답이 되므로 아무거나 출력해도 된다.

처음에는 DP처럼 보여서 DP로 풀었는데 메모이제이션이 제대로 안된다. 산책시킬 최소 횟수의 최대값은 n*k/2이기때문에 메모이제이션을 적용하려면 메모리가 부족할것이다. 그래서 다시 생각해보니 값이 범위가 생각보다 작으므로 그냥 풀어도 될것 같다는 생각이 들어서 연속되는 이틀을 모두 비교하면서 만약 k번 산책을 시키지 못한다면 더 산책을 시켜야 할 만큼 늦게 오는 날에 더 산책을 시키는 방식으로 코드를 작성했다.

#include <stdio.h>
int walk[501], n, k;
int main() {
	int i, count = 0;
	scanf("%d%d", &n, &k);
	for (i = 1; i <= n; i++)
		scanf("%d", &walk[i]);
	for (i = 2; i <= n; i++) {
		if (walk[i - 1] + walk[i] < k) {
			count += k - (walk[i - 1] + walk[i]);
			walk[i] += k - (walk[i - 1] + walk[i]);
		}
	}
	printf("%d\n", count);
	for (i = 1; i <= n; i++)printf("%d ", walk[i]);
}


C. Sanatorium

http://codeforces.com/contest/732/problem/C

이 문제는 못 풀었는데, 라운드가 거의 종료되었을때 감을 잡아서.. 나중에 다시 한번 풀어봐야겠다.

ALGOSPOT - BOGGLE

알고리즘/동적 계획법

문제

https://algospot.com/judge/problem/read/BOGGLE



풀이

동적 계획법 문제같아서 동적 계획법으로 풀었다. 그래프로 풀 수 있지 않을까라는 생각이 들지만 나는 DP로만 풀었으므로 DP 풀이만 적음.

먼저 findAll()과 solve() 두개의 함수를 작성했다. findAll()은 좌표 [0,0]부터 [4,4]까지, 즉 모든 칸에서 입력받은 문자열을 찾을 수 있는지 확인하는 solve()를 실행시키는 함수이다.

solve함수는 세개의 인자를 받는데 각각 게임판의 y좌표, x좌표, 게임판의 y,x 좌표의 문자열과 비교할 찾을 문자열의 index번째 문자다.

메모이제이션은 dp[y][x][index] = 게임판[y][x] 좌표에서 시작해 word[index] 이후의 문자들을 매칭 시킬수 있는가에 대해 메모이제이션을 적용했다. 입력값이 작아서 최대 250크기 만큼의 배열만 사용하므로 3차원 배열을 사용해도 문제가 없었다.


#include <cstdio>
#include <cstring>
char map[5][6],word[11];
int dp[5][5][10];
int solve(int y, int x, int index){
	int i,j;
	//메모이제이션 값 체크. 초기값 -1이 아니라면 바로 리턴
	int& ret = dp[y][x][index];
	if(ret != -1) return ret;
	for(i=-1;i<=1;i++){
		for(j=-1;j<=1;j++){
			//인접한 칸을 검사하며 게임판을 벗어났다면 패스한다.
			if((i==0&&j==0)||y+i<0||y+i>4||x+j<0||x+j>4) continue;

			//매칭되는 문자열을 찾았을때
			if(map[y+i][x+j] == word[index]){
				//다음 문자가 null이라면 즉, 모든 문자를 다 찾았다면 true를 반환한다.
				if(word[index+1] == '\0') return ret = 1;
				//아직 다 찾지 못했으므로 현재 위치에서 시작하는 다음 문자를 찾는 함수를 재귀 호출한다.
				ret = solve(y+i,x+j,index+1);
				//만약 현재 위치에서 문자열 매칭에 성공했다면 더 찾을 필요가 없으므로 바로 1를 반환한다.
				if(ret==1) return ret;
			}
		}			
	}
	//여기까지 왔다면 문자를 찾지 못한것이므로 0을 반환한다.
	return ret = 0;
}
int findAll(){
	int i,j;
	for(i=0;i<5;i++){
		for(j=0;j<5;j++){
			int& ret = dp[i][j][0];
			if(ret != -1) return ret;
			if(map[i][j] == word[0]){
				ret = solve(i,j,1);
				if(ret) return ret;
			}
		}
	}
	return 0;
}
int main(){
	int i,j,t,n;
	scanf("%d",&t);
	while(t--){
		for(i=0;i<5;i++)
			scanf(" %s",map[i]);
		scanf(" %d",&n);
		while(n--){
			memset(dp,-1,sizeof(int)*250);
			scanf(" %s",word);
			printf("%s %s\n",word,findAll()?"YES":"NO");
		}
	}
}