알고리즘(땅따먹기, 폰켓몬, 숫자의 표현)

[땅따먹기]

 

* 로직

• 현재 행 기준으로 이전 행의 값들 중에서(같은 열 제외) 최댓값을 뽑고, 현재 행의 값과 더해 갱신해준다
  
  ex. 2행 1열의 경우,
  1행 2열, 1행 3열, 1행 4열 중 최대 점수를 뽑고(max), dp[2][1] = max + land[2][1]로 갱신한다
  
  
• dp[i][j] : i, j까지 얻어진 최대 점수

 

// 땅따먹기
public class Problem_ConquerGround {

    public static void main(String[] args) {
        int[][] land = {
                {1,2,3,5},{5,6,7,8},{4,3,2,1}
        };
        int answer = solution(land);
        System.out.println(answer);
    }

    public static int solution(int[][] land) {
        int answer = 0;
        int N = land.length;
        int M = 4;

        int[][] dp = new int[N][M];
        for(int j=0; j<M; ++j) {
            dp[0][j] = land[0][j];
        }

        for(int i=1; i<N; ++i) {
            for(int j=0; j<M; ++j) {
                for(int a=0; a<M; ++a) {
                    if(j != a) {
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][a] + land[i][j]);
                    }
                }
            }
        }

        // 맨 마지막 행에서 최댓값 얻기
        for(int j=0; j<M; ++j) {
            answer = Math.max(answer, dp[N-1][j]);
        }

        return answer;
    }
}

 

 

---

[폰켓몬]

* 로직

• 주어진 입력들에 대해 중복된 수를 없애주기 위해 HashSet 사용
• HashSet을 통해 폰켓몬의 종류를 구할 수 있다
• 폰켓몬의 종류 개수가 뽑아야되는 개수보다 작다면 -> 폰켓몬의 종류를 답에 넣는다
• 폰켓몬의 종류 개수가 뽑아야되는 개수보다 크거나 같다면 -> 뽑아야되는 개수를 답에 넣는다 

// 폰켓몬
import java.util.HashSet;

public class Problem_Phonekemon {

    public static void main(String[] args) {
        int[] nums = {3,3,3,2,2,4};
        int answer = solution(nums);
        System.out.println(answer);
    }

    public static int solution(int[] nums) {
        int answer = 0;
        int N = nums.length;
        int pickNum = N/2;

        HashSet<Integer> hashSet = new HashSet<>();
        for(int num : nums) {
            hashSet.add(num);
        }

        if(hashSet.size() > 0) {
            // 폰켓몬 종류가 뽑아야되는 개수보다 작을 때
            if(hashSet.size() < pickNum) answer = hashSet.size();

            // 폰켓몬 종류가 뽑아야되는 개수 이상일 때
            else answer = pickNum;
        }

        return answer;
    }
}

 

 

---

[숫자의 표현]

* 로직

• 투 포인터 알고리즘(idx1, idx2)을 사용한다
• 누적 값(acc)를 기준으로
  • acc < n 이라면 -> idx2를 증가시키고, acc += idx2
  • acc == n 이라면 -> 답을 카운팅, idx2를 증가시키고 acc += idx2
  • acc > n 이라면 -> idx1을 증가시키고, acc -= idx1
• 처음 answer=1로 한 이유는 idx2가 n과 같아진 이후에는 다른 경우를 고려할 필요가 없기 때문에 미리 n에 도달한 경우를 카운팅해준거라고 생각하면 된다

 

// 숫자의 표현
public class Problem_RepresentNum {

    public static void main(String[] args) {
        int n = 15;
        int answer = solution(n);
        System.out.println(answer);
    }

    public static int solution(int n) {
        int answer = 1;

        // 투 포인터 알고리즘
        int idx_1 = 0;
        int idx_2 = 0;
        int acc = 0;
        while (idx_2 < n) {
            if(acc < n) {
                acc += ++idx_2;
            }

            else if(acc == n) {
                answer++;
                acc += ++idx_2;
            }

            // acc가 커진다면
            else {
                acc -= ++idx_1;
            }
        }

        return answer;
    }
}