작성
·
187
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)의 정의에 맞는 코드가 됩니다.