251013

lililllilillll·2025년 10월 13일

개발 일지

목록 보기

323/350

✅ 한 것들

프로그래머스
백준
R&D : Jenkins, Flat Kit

⚔️ 프로그래머스

공 이동 시뮬레이션

long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {    
    // 시작점은 정해져 있지 않고, 도착점만 정해져 있으므로 도착점에서부터 집계 시작    
    // 오른쪽으로 최대치 가고 위쪽으로 최대치 가는 쿼리가 있다면, 어디서 시작해도 된다
    // 벽에 부딪히지 않고 이동한다면 가능한 시작점은 한 곳
    
    // x축 하나만 있고, 시작점이 0이라고 가정
    // 왼쪽과 오른쪽으로 도달한 범위가 있을 것
    // 왼쪽 최대치에 닿는다면, 시작점이 왼쪽으로 1칸 갈 수록 오른쪽으로 1칸씩 옮겨지는 효과
    
    // 시작점의 범위가 벽을 넘어간다면, 시작점의 범위는 반대 방향으로 늘어난다.
    // 도착점에서부터 쿼리를 역순으로 실행하며, 시작점의 범위를 옮겨간다.
    // 이는 행과 열에 대해 따로따로 진행한다.
    
    // 왼쪽으로 가는 쿼리를 역진행
    // 
    // 최소 도착 범위가 0이 아니다
    //   그대로 오른쪽으로 옮긴다
    //   옮겼는데 최대가 m-1보다 크면 축소한다
    //   옮겼는데 최소가 m-1보다 크면 불가능 처리
    // 
    // 최소 도착 범위가 0이다
    //   최대 + dx가 새로운 최대가 된다
    
    pll sIRange = {x,x};
    pll sJRange = {y,y};
    ll newMin, newMax;
    
    // 쿼리를 역순으로 재생하면서 가능한 범위 탐색
    for(int i=size(queries)-1; 0<=i; i--)
    {
        int q=queries[i][0], dx = queries[i][1];
        switch(q)
        {
            // 실수 : 여기서 sIRange랑 sJRange 순서 바꿔서 사용함
            case 0: // 왼쪽 (j 감소) → 역순이니 j 증가
                newMin = (sJRange.first==0) ? 0 : sJRange.first+dx;
                newMax = min(sJRange.second+dx, (ll)m-1);
                sJRange = {newMin, newMax};
                break;
            case 1: // 오른쪽 (j 증가)
                newMin = max(sJRange.first-dx,(ll)0);
                newMax = (sJRange.second==m-1) ? m-1 : sJRange.second-dx;
                sJRange = {newMin, newMax};
                break;
            case 2: // 위쪽 (i 감소)
                newMin = (sIRange.first==0) ? 0 : sIRange.first+dx;
                newMax = min(sIRange.second+dx, (ll)n-1);
                sIRange = {newMin, newMax};
                break;
            case 3: // 아래쪽 (i 증가)
                newMin = max(sIRange.first-dx,(ll)0);
                newMax = (sIRange.second==n-1) ? n-1 : sIRange.second-dx;
                sIRange = {newMin, newMax};
                break;
        }
        
        if (sIRange.first >= n || sIRange.second < 0 || sJRange.first >= m || sJRange.second < 0) { return 0; }
        if(sIRange.first==0 && sIRange.second==m-1 && sJRange.first==0 && sJRange.second==n-1) { break; }
    }

    return (sIRange.second - sIRange.first + 1) * (sJRange.second - sJRange.first + 1);
}

⚔️ 백준

9251 LCS

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

namespace
{
	int LCS(string& org, string& cmp)
	{
		vvi dp = vvi(cmp.size()+1, vi(org.size()+1, 0));
		for (int i = 1; i <= cmp.size(); i++)
		{
			for (int j = 1; j <= org.size(); j++)
			{
				if (org[j - 1] == cmp[i - 1])
				{
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				else
				{
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		return dp[cmp.size()][org.size()];
	}
}

void B9251::Solution()
{
	string str1, str2;
	cin >> str1;
	cin >> str2;
	cout << LCS(str1, str2);
}