알고리즘 스터디 후기 / 내 문제점 기록

알고리즘 스터디를 처음 해봤다

여러 사람들이 모여 서로 피드백을 해주는 모습을 기대 했다

하지만 스터디원은 엄청난 고인물이셨고

나는 피드백을 받을수 있었지만 내가 피드백을 해줄수는 없었다

 

DP기초문제를 풀고나서 

해결 과정을 이야기 하려고 했다 

하지만 답을 봐야할때 고집이생겨 시간안에 해결하지 못했고 

스티디원분이 솔루션을 주셨다

 

설명을 해주실때 이해하는대 시간이 오래 걸려서

원인을 되짚어봤다

 

문제는 백준 2579 를 자바로 풀었으며

스터디 시간 제외 4시간 정도 걸렸다

스터디 하기전 3시간 스터디 후 1시간

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

2579번: 계단 오르기

 

가장큰 문제점이

내가 문제를 이해 했다고 생각하는 깊이 같았다

나는 이 문제를 배열을 사용해서 최댓값을 갱신해 나가면 풀수 있겠구나 였고

스터디원의 솔루션은 갱신 하되 3번 연속된 계단을 밟을수 없다는 조건때문에

2차원배열로 경우의 수를 나눠야 한다는것이였다

 

내가 예상했던 풀이 방식과 다른 모양이었다

문제를 잘못 이해한 상태에서 코드를 같이 작성 한다는것 때문에

시간이 딜레이 되었다

스터디가 끝난후 혼자 천천히

문제를 다시읽었다

이 경우  1칸을 이동했을경우 다시 한칸을 이동하게 되면

원래 계단에서 1칸이동으로 이미 2개의 계단이 연속 되고

다시한칸 이동할경우 계단이 3번 연속 되기때문에

2차원 배열에 연속 되는 카운트정보를 추가해 3연속 예외를 다루자는 말이었다

 

문제가 이해될수록 스터디원의 설명도 같이 이해가 됐다

이것때문에 dp[i] state 의 이해를 설명했구나

하지만 나는 점화식을 만드려고 했구나 등등..

 

 

한문제를 오래 붙잡지 말라는 말도 있었고

완벽하게 이해하기 전 까진 키보드에서 손을 때야한다 던가

스터디원분이 해주셨던 말씀중에 나에게 필요한 좋은 이야기가 많았다

빨리 파이팅해서 좋은 상호작용이 될수 있도록 해야겠다

 

++ 문제 설명

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
int[] sta = new int[num];//실제 stairs
int[][] dp = new int[num][3];//가상 DP
for (int i=0;i<num; i++){ //입력
    sta[i]= Integer.parseInt(br.readLine());
}
br.close();
//dp[i][j] = i번째 계단까지 도착했고 j개의 연속된 계단을 밟았을 때 최대값
int j=1;
dp[0][j]=sta[0];

if (num >=2){//num이 1일경우 dp[0][j]=sta[0]; 를 바로 출력
    dp[1][j]=sta[0]+sta[1];
    dp[1][j+1]=sta[1];
    for (int i=2; i<num;i++){
        dp[i][j] = dp[i-1][j+1] + sta[i];//1칸을 이동 했던 경우, 더이상 한간을 이동할수 없다
        dp[i][j+1] = Math.max(dp[i-2][j], dp[i-2][j+1]) + sta[i];//i로 올때 2칸을 이동했던 경우
    }
}
System.out.println(Math.max(dp[num-1][j],dp[num-1][j+1]));

버퍼리더를 사용했으며 2차원 배열로 연속정보를 다뤘다

나름 가독성을 좋게 하려고 0부터 시작하지만 1을 1칸, 2를 2칸 움직였을때 라고 설정했다

dp[i] = 이동하기전 최댓값 + 현재 계단의 값 이다

여기에 [j]값을 더해

[j]에 한번움직였을때만 3번 연속된 경우를 제외하여 최댓값을 갱신,

[j+1] 에 두번 움직였을때는 연속성이 끊어지기때문에 그저 큰값을 더해주면 된다

그후 j 와 j+1중 큰값을 출력한다

 

+  num(계단값)이 1일경우를 if 로 분리 해주었다

궁금한점은

 이것이 좋은 예외처리 라고 할수 있을지,

j를 좀더 깔끔하게 사용할수 있었을지 이다