백준 11058 JAVA

문제 유형

• DP

문제 접근

• 답
  • 최대 A의 개수
• 주어지는 정보
  • A 출력
  • A 복사, 붙여넣기
• 활용 방안
  • dp[i] = dp[i-1] + 1
  • dp[i] =
    • dp[i-3] * 2
    • or
    • dp[i-4] * 3
    • or
    • dp[i-5] * 4
    • or

    (복사 붙여넣기는 3번의 커맨드가 필요하다. 커맨드 이후에는 붙여넣기라는 커맨드 1개만 사용하면 되니, 위와 같은 공식이 성립한다)

맞는 답안

import java.util.*;



public class Main {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int N = scanner.nextInt();
        
        long[] dp = new long[N+1];
        
        for(int i = 1; i<=N; i++)
        {
            dp[i] = dp[i-1] + 1;
            
            int cnt = 2;
            for(int j = i-3; j>=1; j--)
            {
                dp[i] = Math.max(dp[i], dp[j]*cnt++);
            }
        }
        
        
        System.out.println(dp[N]);
        
    }
}

 

 

나의 틀린 답안

내가 생각한 문제 접근

• 답
  • 최대 A의 개수
• 주어지는 정보
  • A 출력
  • A 복사, 붙여넣기
  ⇒ 3개의 선택지 구성 사능
  • A 출력
  • A 붙여넣기
  • A 복사, 붙여넣기
• 활용 방안(BFS + DP)
  • BFS
    • 3개의 선택지를 BFS로 구성
    • 각 선택지에 따른 DP[current]의 값이 최대가 되도록 함수 구성
• 오답인 이유
  • 모든 경우의 수를 고려하지 않았다.
    • ex) dp[7] 의 값을 구하라
      • dp[6]+1
      • dp[6] + A의 복사된 값
      • dp[4] * 2
      ⇒ 이런 식의 선택지로 구성됨. 다른 dp[i]의 값에서부터 형성된 dp[7]이 더 클 수 있으므로 예외 발생 가능.

• 3개의 선택지는 실행 과정에서 논리적 오류가 발생한다.
  • 예시 상황)
    • a의 선택지로 만들어진 dp[x]가 있다.
    • b의 선택지로 dp[x]가 더 큰 값이 됐다.
    • a의 선택지에 복사값은 b의 선택지보다 크다.
  • 이 상황에서, dp[x]는 a의 복사값으로 dp[x+a] = dp[x] + copy값을 가지는 경우가 발생한다.
  • 이런 예시는 논리적으로 틀린 상황이다. b의 선택지에서 만들어진 dp[x]의 값에 a선택지의 복사값이 사용됐기 때 문이다.

 

 

a 선택지에서 cur.copy = 4가 되어 dp[7] = 8을 형성했다.

그리고 b 선택지에서 dp[7]=9가 되었다. 이 상황에서 dp[7+1]= dp[7] + cur.copy = 13이 되는 상황이 벌어진다(cur.copy = a 선택지의 cur.copy =4)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;

class Data
{
    public int count;
    public int copy;
    
    Data(int count, int copy)
    {
        this.count = count;
        this.copy = copy;
    }
}

public class HelloWorld {
    
    public static int N;
    public static int[] dp = new int[101];
    
    //make : dp
    public static void bfs()
    {
        Queue<Data> q = new LinkedList<>();
        
        //0 is printing A - 1 count
        //1 is copying A - 3 count
        
        q.add(new Data(0,0));
        while(!q.isEmpty())
        {
            Data cur = q.peek();
            q.remove();
            
            for(int choice = 0; choice < 3; choice++)
            {
                if(choice == 0 && cur.count+1 <= N)
                {
                    if(dp[cur.count+1] < dp[cur.count] + 1)
                    {
                        dp[cur.count+1] = dp[cur.count] + 1;
                        q.add(new Data(cur.count+1, cur.copy));
                    }
                }
                
                else if(choice == 1 && cur.count+1 <= N)
                {
                    if(dp[cur.count+1] < dp[cur.count] + cur.copy)
                    {
                        dp[cur.count+1] = dp[cur.count] + cur.copy;
                        q.add(new Data(cur.count+1, cur.copy));
                    }
                }
                
                else if(choice == 2 && cur.count+3 <= N)
                {
                    if(dp[cur.count+3] < dp[cur.count]*2)
                    {
                        dp[cur.count+3] = dp[cur.count]*2;
                        int copy = dp[cur.count];
                        q.add(new Data(cur.count+3, copy));
                    }
                }
            }
        }
    }
    
    public static int FindMaxDp()
    {
        int max = 0;
        for(int i = 0; i<=N; i++)
        {
            System.out.println(dp[i]);
            if(max < dp[i])
            {
                max = dp[i];
            }
        }
        
        return max;
    }
    
    
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        N = scanner.nextInt();
        
        bfs();
        int max = FindMaxDp();
        
        System.out.println(max);
    }
}