[Java] SWEA 4311번 : [연습문제] 오래된 스마트폰*

1. 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWL2vlPKMlQDFAUE 

SW Expert Academy

 

 

 

2. 풀이과정

*라이브러리는 Scanner외에 사용할 수 없게 되어있다.

숫자를 담을 배열은 최대 999까지 있으므로 크기를 1000으로 잡아준다.

가능한 숫자가 0, 1이라면  10, 11, 100, 110, 101, 111를 사용 가능한 숫자로 넣어줄 것이기 때문이다.

 

이때 10같은 경우는 2번, 100같은 경우는 3번 터치해야 하며, 이 값은 values에 기록한다.

values에서 터치수가 1인 값부터 가능한 연산을 반복문을 돌며 수행해준다.

연산을 해주다가 W의 터치수가 현재 검토중인 터치수보다 작아지면 멈춘다. 앞으로 터치가 증가하는 경우 밖에 남지 않았기 때문이다.

 

예)

사용 가능한 수 = 1 2 3

사용 가능한 연산 = +, -, *, /

W = 5

 

1. 사용 가능한 수 업데이트 & values(터치수) 업데이트

1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33, 111, 112, 113, 121, 122, 123, ... 333해당 수마다, 터치 수를 values에 기록한다. 아래 그림에서 파란 글씨에 해당하는 값이다.연산없이 W가 될 수 있으면 출력하고 넘어간다.

 

2. 터치수 1부터 M까지 확인하면서 해당 수의 터치수와 일치하면 종료한다.

터치수가 1일 때, 실행하면 결과는 아래와 같다. 다음은 터치수가 2인 값을 보고 다음 터치수가 3인 값을 보는데 W가 되기 위한 터치수와 일치하므로 종료한다.

연산을 했으므로 마지막에 '='를 붙여서 +1을 해주고 출력한다.

 

 

 

import java.util.Scanner;

class Solution
{
	public static int operation(int n1, int n2, int op) {
		int result = -1;
		switch(op) {
		case 1:
			result= n1+n2;
			break;
		case 2:
			result= n1-n2;
			break;
		case 3:
			result= n1*n2;
			break;
		case 4:
			if(n2>0)
				result= n1/n2;
			break;
		}
		return result;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		final int INF = 999_999_999;
        
		for(int t=1; t<=T; t++) {
			int values[] = new int[1000];
			for(int i=0; i<1000;i++) {values[i]=INF;}
			int N = sc.nextInt();
			int O = sc.nextInt();
			int M = sc.nextInt();
			
			int su[] = new int[1000];
			int size = N;
			for(int i=0; i<N; i++) {
				su[i]=sc.nextInt();
				values[su[i]]=1;
			}
			int oper[] = new int[O];
			for(int i=0; i<O; i++) {
				oper[i] = sc.nextInt();
			}
			int W = sc.nextInt();
			//연산X
			if(values[W]<INF) {
				System.out.println("#"+t+" 1");
				continue;
			}
			int now = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					now = su[j]*10+su[i];
					if(su[j]!=0) {
						values[now]=2;
						su[size++] = now;
					}
					for(int k=0; k<N; k++) {
						if(su[k]==0) {continue;}
						int next = now + su[k]*100;
						values[next]=3;
						su[size++]=next;
					}
				}
			}
			if(values[W]<INF) {
				System.out.println("#"+t+" "+values[W]);
				continue;
			}
			//연산O
			outloop:for(int m=1; m<=M; m++) {
				for(int i=0; i<=999; i++) {
					if(values[i]==m) {
						if(values[W]<=m) {
							break outloop;
						}
						for(int j=0; j<size; j++) {
							for(int k=0; k<O; k++) {
								int result = operation(i, su[j], oper[k]);
								if(result<0||result>999) {//범위를 넘으면
									continue;
								}
								int temp = m+values[su[j]]+1;
								if(temp<values[result]) {
									values[result]=temp;
								}
							}
						}
					}
				}
			}
			values[W]++;
			if(values[W]>M) {
				System.out.println("#"+t+" -1");
			}
			else {
				System.out.println("#"+t+" "+values[W]);
			}
		}
	}
}