• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

알파코드 질문드립니다.

23.09.13 11:51 작성 조회수 140

0

import java.io.*;
import java.util.*;

public class Main {
	public static int[] dy;
	public int solution(String s){
		int answer = 0;

		dy= new int[101];
		answer = dfs(0,s);
		return answer;
	}
		
	public static int dfs(int s, String str) {
		if(dy[s]>0 ) return dy[s];
		if(s<str.length() && str.charAt(s)=='0') return 0;
		if(s==str.length()-1 || s==str.length()) return 1;
		else {
			int res = dfs(s+1, str);
			String num = str.substring(s,s+2);
			if(Integer.parseInt(num)>26) return 0; //26보다 크면 리턴
			else return res += dfs(s+2, str); //그렇지 않다면 재귀
		}
	}
	public static void main(String[] args){
		Main T = new Main();
		System.out.println(T.solution("25114"));
		System.out.println(T.solution("23251232"));
		System.out.println(T.solution("21020132"));
		System.out.println(T.solution("21350"));
		System.out.println(T.solution("120225"));
		System.out.println(T.solution("232012521"));
	}
}

 

이 코드에서 if(Integer.parseInt(num)>25) return 0 코드랑

if(Integer.parseInt(num)<=26) res+=dfs(s+2, str)랑 차이가 있나요??

 

num이 25보다 크면 리턴해주고 그렇지 않을때 res+=dfs(s+2, str)해준다는 거랑 다른 의미인가요??

 

 

 

답변 1

답변을 작성해보세요.

0

안녕하세요^^

영상의 1분 20초 경 DFS(i)의 정의를 잘 생각해보세요.

위에 코드는 아래와 같이 수정하면 됩니다.

import java.io.*;
import java.util.*;

public class Main {
	public static int[] dy;
	public int solution(String s){
		int answer = 0;

		dy= new int[101];
		answer = dfs(0,s);
		return answer;
	}
		
	public static int dfs(int s, String str) {
		if(dy[s]>0 ) return dy[s];
		if(s<str.length() && str.charAt(s)=='0') return 0;
		if(s==str.length()-1 || s==str.length()) return 1;
		else {
			int res = dfs(s+1, str);
			String num = str.substring(s,s+2);
			if(Integer.parseInt(num)>26) return res; //26보다 크면 리턴
			else return res += dfs(s+2, str); //그렇지 않다면 재귀
		}
	}
	public static void main(String[] args){
		Main T = new Main();
		System.out.println(T.solution("25114"));
		System.out.println(T.solution("23251232"));
		System.out.println(T.solution("21020132"));
		System.out.println(T.solution("21350"));
		System.out.println(T.solution("120225"));
		System.out.println(T.solution("232012521"));
	}
}

위에서 if(Integer.parseInt(num) > 26) return res; 를 해주어야 DFS(i)의 정의에 맞는 코드가 됩니다.