부트캠프 76일차 후기

그동안 해결책이 떠오르지 않았던 문제를 드디어 풀었다. 골드 상위 DP 문제 였는데, 아이디어를 살짝만 수정하면 풀 수 있는 문제였음에도 지금까지 끙끙되었던게 허무할 지경이다. 그래서 이 문제에 대해 간단하게 정리해보고자 한다.

 

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

1513번: 경로 찾기

아이디어 자체는 금방 떠올렸다. 문제 자체는 DP 문제이고, 좌표가 50 이하의 자연수이니까, 이것을 dp에 사용할 수 있을 것이다. 그리고 오락실에 방문한 수 또한 50이하의 자연수. 즉, 정보를 조합하면 최대 50의 4승만큼의 메모이제이션이 가능할 것이다라 예측했다.

 

내가 DP를 풀 때, 늘 생각을 하는 것이 있는데, 만약 경우의 수가 여러 개가 있을 때, 일단 가보고, 현재의 상태를 숫자로 나타낼 수 있다면, 이 상태를 인덱스화해서 배열 안에 현재의 상태를 저장하고, 만약 똑같은 상태가 들어오면, 저장된 상태를 가져온다. 란 방식을 먼저 생각한다.

 

그래서, 이번에도 마찬가지이다. 현재 상태를 좌표인 r과 c로 나타낸다. 특정 오락실에 갈 수 있을 판단하기 위해서, 지금까지 간 오락실 중 가장 큰 오락실 번호를 저장한다. 그리고 정답을 위해서, 그동안 방문한 오락실 갯수를 저장한다. 늘 하던 방식이면, 이렇게 된다.

dp[y][x][previousPlayRoom][playRoomCount]

// y, x는 현재 위치, previousPlayRoom은 최대 오락실 번호, playRoomCount는 오락실 방문 수

하지만, 여기서부터가 문제였다. 이렇게 하더라도 어떻게 0개, 1개, 2개...N개 등등의 갯수를 어떻게 저장할 것인가?이다. 여기까지는 늘 하던 방식이라서, 어렵지 않았지만, 이것을 어떻게 내가 원하는 정보로 가공을 할지가 문제였다.

 

처음에는 목적지에서 갯수를 합친다는 방식을 시도해보았지만, 결국 실패했다. 결국 고민 끝에 관련 정보를 찾아보았고, dp의 개념을 약간 수정하면 된다는 사실을 알게 되었다. 기존의 playRoomCount를 오락실 방문 수가 아닌, 목표로 하는 오락실 방문 수로 바꾸면 된다.즉,

solve(1, 1, P[1][1], (P[1][1] > 0))

// 기존의 탐색을 위한 코드


for(int i = 0; i <= C; i++)
	solve(1, 1, P[1][1], i - (P[1][1] > 0))
    
// 새로운 코드

이런 식으로 수정하고, 마지막에 목표를 달성했을 때, count가 0인지만 확인하면 된다.

그렇게 완성된 코드는 다음과 같다.

 

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

const int MOD = 1000007;
int N, M, C, dp[51][51][51][51], P[51][51], X, Y;

int solve(int y, int x, int prv, int cnt)
{
	if (cnt < 0) return 0;
	int& ret = dp[y][x][prv][cnt];
	if (y == N && x == M)
	{
		return ret = (cnt == 0);
	}
	if (ret >= 0) return ret;
	ret = 0;
	if (y < N)
	{
		if (P[y + 1][x] == 0) ret += solve(y + 1, x, prv, cnt) % MOD;
		if (P[y + 1][x] > prv && cnt > 0) ret += solve(y + 1, x, P[y + 1][x], cnt - 1) % MOD;
	}
	if (x < M)
	{
		if (P[y][x + 1] == 0) ret += solve(y, x + 1, prv, cnt) % MOD;
		if (P[y][x + 1] > prv && cnt > 0) ret += solve(y, x + 1, P[y][x + 1], cnt - 1) % MOD;
	}
	ret %= MOD;
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(dp, -1, sizeof(dp));
	cin >> N >> M >> C;
	for (int i = 1; i <= C; i++)
	{
		cin >> X >> Y;
		P[X][Y] = i;
	}
	for(int i = 0; i <= C; i++) 
		cout << solve(1, 1, P[1][1], i - (P[1][1] > 0)) << " ";
	cout << '\n';
}

결국 지금까지 나를 괴롭힌 문제는 이렇게, 허무하게 풀리게 되었다..

 

오늘로 드디어, MVP를 완성하였다. 오늘은 완성한 코드를 테스트 해보며 디버깅을 하는 과정을 거쳤다. 대부분 사소한 오류였는데, 하나 알게 된 것은 Controller에서 리턴 타입을 명시하지 않고 리턴을 해도, 오류가 발생하지 않고, 그냥 아무것도 리턴하지 않는다. 그래서, 내가 테스트를 할때, 아무것도 리턴하지 않아서 당황하였다. 그래도 막상 해결책을 알게되니 허무하기도 하다.

 

가장 기억에 남는 것은 @ManyToOne에서 CascadeType.ALL 을 쓰다가, 자식 엔티티가 삭제되었을 때, 부모 엔티티가 삭제되어서, 제대로 작동이 안 된 것이였다. 이게 문제가 되어서, 내가 엔티티를 만들고 삭제하였을 때, 멤버가 삭제되어서 Token을 통해 얻은 멤버 정보가 없어서 문제가 발생하였다.

 

나는 이것 때문에 양방향으로 바꾸는 것이 귀찮아서, 관련 정보를 찾아보았는데, OnDelete가 사용하기 좋은 것을 발견하였다. 그렇게 엔티티가 삭제 되었을 때의 연관 관계 문제를 해결하였다.

@Entity
class Comment(
    var commentText: String,
    @ManyToOne(fetch = FetchType.LAZY)
    @OnDelete(action = OnDeleteAction.CASCADE)
    val board: Board,
):

내일부터 부가기능을 추가할 예정이다. 그리고, 튜터님에게 코드리뷰를 부탁해보자.