[ 프로그래머스 | 2022 kako tech internship ] 코딩 테스트 공부 문제 풀이 c++

https://school.programmers.co.kr/learn/courses/30/lessons/118668

프로그래머스

DP를 잘 활용하고, 인덱스와 조건을 유심히 다룬다면 원활하게 풀 수 있는 문제 !

아래는 오답 분석 및 문제 해결 접근 방법이다.

 

문제 풀이

 

모든 문제를 풀기 위해 달성해야하는 알고력, 코딩력의 최대값에 도달해야한다.

 

위 목표에 도달하기 위해서  a[알고력][코딩력]이라는 배열을 만들어주고, 해당 index에 도달하기 위한 최단 시간을 업데이트하며 dp를 진행한다.

---

오답 분석

 

처음에 여기까지 아이디어를 도출하는 것은 성공했으나, 

 

1) 표를 채우는 과정에서 다음 열 또는 행을 현재 값을 이용해 채우는 것[바텀업]이 아닌, 이전 열 또는 행으로부터 현재 인덱스의 표를 채우려고 했기에[탑다운] 인덱스에러를 해결하기 어려웠다. -> 이는 바텀업 방식을 통해 고칠 수 있다. (바텀업을 사용한다면, 배열의 최댓값에 다다갔을 때의 문제점에 대해 더 유심히 생각해야한다.)

탑다운, 잘못된 접근 방식

a[i][j]=min(a[i-1][j],a[i][j-1])+1 // 탑다운 x 
a[i][j+1]=min(a[i][j+1],a[i][j]+1) // 바텀업 o -> 초기값은 INF

 

2) 또한 dp 배열 크기의 최댓값을 150x150으로 지정해 풀려고 했지만 이는 효율성 검사를 통과하지 못한다. -> 즉 벡터를 통해 유동적으로 현재의 알고력, 코딩력 ~ 목표하는 알고력, 코딩력을 채울 수 있도록 해야한다.

vector<vector<int>> a(n+1, vector<int>(m+1,1e9));// n x m 크기의 알고력 x 코딩력을 달성하는 데 걸리는 시간을 저장

 

추가로 더 고려했어야할 부분이 ..

 

 

3) 이미 주어진 알고력, 코딩력으로 모든 문제를 해결할 수 있는 경우와 (초기상태 주의하기)

 

4) 굳이 0,0부터 채우지 않아도, 지금 주어진 알고력, 코딩력부터 목표하는 값만 채워도 되었다는 점이다. (메모리 효율성)

 

5) 마지막으로 표를 갱신하는 과정에서 목표하는 알고력, 코딩력이 넘을 경우에는 인덱스 에러가 날 수 있기에 적절하게 min값을 활용해 업데이트를 해줘야한다!

if(p[0]<=i && p[1]<=j){
	a[min(i+p[2],n)][min(j+p[3],m)] // 현재 접근하는 인덱스는 a 배열 사이즈 최대값인 n,m을 넘어선 안됨
   		 =	min(a[min(i+p[2],n)][min(j+p[3],m)],
    			a[min(i,n)][min(j,m)]+p[4]);   
}

---

전체 코드

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int i,j,k;
int solution(int alp, int cop, vector<vector<int>> problems) {
    n=-1; m=-1;
    for(auto p: problems){ // 알고력, 코딩력의 최댓값을 각각 n,m에 저장
        if(n<p[0]){
            n=p[0];
        }
        if(m<p[1]){
            m=p[1];
        }
    }
    if(alp>=n && cop>=m){ // 이미 달성한 경우는 0의 시간이 걸림
        return 0;
    }
    vector<vector<int>> a(n+1, vector<int>(m+1,1e9));// n x m 크기의 알고력 x 코딩력을 달성하는 데 걸리는 시간을 저장
    
    // 코딩력, 알고력 중 하나만 이미 달성한 경우엔 최댓값이 이미 달성한 것으로 생각 (아래 for문을 위해)
    if(alp>n){
        alp=n; 
    }
    if(cop>m){
        cop=m;
    }
    a[alp][cop]=0;
    for(i=alp;i<=n;i++){
        for(j=cop;j<=m;j++){
            if(j+1<=m){  //알고리즘 공부
                a[i][j+1]=min(a[i][j]+1,a[i][j+1]);
            }
            if(i+1<=n){ //코딩공부
                a[i+1][j]=min(a[i][j]+1,a[i+1][j]);
            } 
            // 문제를 푸는 경우
            for(auto p:problems){
                if(p[0]<=i && p[1]<=j){
                    a[min(i+p[2],n)][min(j+p[3],m)]=min(a[min(i+p[2],n)][min(j+p[3],m)],a[min(i,n)][min(j,m)]+p[4]);   
                }
            }
        }
    }
    int answer=a[n][m];
    return answer;
}

 

 

잘하고 싶다 !!