[BOJ] 14226. 이모티콘

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		int dist[][] = new int[S+1][S+1];

		for (int i = 0; i <= S; i++) {
			Arrays.fill(dist[i], -1);
		}
		
		Queue<Integer> q = new LinkedList<>();
		int s = 1;
		int c = 0;
		q.add(s);
		q.add(c);
		dist[1][0]=0;
		while (!q.isEmpty()) {
			s = q.poll();
			c = q.poll();
			if (dist[s][s] == -1) {
				dist[s][s] = dist[s][c] + 1;
				q.add(s); q.add(s);
			}
			if (s+c<=S && dist[s+c][c] == -1) {
				dist[s + c][c] = dist[s][c] + 1;
				q.add(s + c); q.add(c);
			}
			if (s - 1>=0 && dist[s - 1][c] == -1) {
				dist[s - 1][c] = dist[s][c] + 1;
				q.add(s - 1); q.add(c);
			}
		}

		int ans = Integer.MAX_VALUE;
		
		for (int i = 0; i <=S ; i++) {
			if (dist[S][i]!=-1 && ans > dist[S][i]) {
				ans = dist[S][i];
			}
		}
		System.out.print(ans);
	}
}