PI solve

[Sprexatura]

http://algospot.com/judge/problem/read/PI

를 푸시면 됩니다 :)

[mewards]

이클립스에서는 잘 돌아가는데 알고스팟에서는 nonzero return code 런타임 에러가 발생하는데 어떻게 해결해야 하는지 잘 모르겠네요. java로 했습니다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<String> num = new ArrayList<>();
        int cases = sc.nextInt();
        while (cases-- > 0) {
            String input = sc.next();
            num.add(input);
        }
        // int numInt = Integer.parseInt(num);
        for (int i = 0; i < num.size(); i++) {
            String now = num.get(i);
            int sum = 0;
            while (now.isEmpty() != true) {
                int three = 11, four = 11, five = 11;
                if (now.length() > 5) {
                    three = chk(now.substring(0, 3));
                    four = chk(now.substring(0, 4));
                    five = chk(now.substring(0, 5));
                } else if (now.length() == 4) {
                    four = chk(now.substring(0, 4));
                } else {
                    three = chk(now.substring(0, 3));
                }
                if (five > four) {
                    if (four > three) {
                        now = now.substring(3);
                        sum += three;
                    } else {
                        now = now.substring(4);
                        sum += four;
                    }
                } else if (five == four) {
                    if (four > three) {
                        now = now.substring(3);
                        sum += three;
                    } else {
                        now = now.substring(5);
                        sum += five;
                    }
                } else {
                    if (three < five) {
                        now = now.substring(3);
                        sum += three;
                    } else {
                        now = now.substring(5);
                        sum += five;
                    }
                }
            }
            System.out.println(sum);
        }
        sc.close();
    }

    static public int chk(String str) {
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            int each = Integer.parseInt(str.substring(i, i + 1));
            arr.add(each);
        }
        int diff = arr.get(1) - arr.get(0);
        if (diff == 0) {
            for (int i = 2; i < arr.size(); i++) { // 11111
                if (arr.get(i - 1) == arr.get(i)) {
                    if (i == arr.size() - 1)
                        return 1;
                    else
                        continue;
                } else
                    return 10;
            }
        } else {
            if (arr.get(0) == arr.get(2)) {
                if (arr.size() == 5) {
                    if (arr.get(0) == arr.get(4) && arr.get(1) == arr.get(3))
                        return 4;
                    else
                        return 10;
                } else if (arr.size() == 4) {
                    if (arr.get(1) == arr.get(3))
                        return 4;
                    else
                        return 10;
                } else {
                    return 4;
                }
            } else {
                if (arr.get(1) - arr.get(0) == arr.get(2) - arr.get(1)) {
                    if (diff == 1 || diff == -1) {
                        if (arr.size() == 5) {
                            if (arr.get(3) - arr.get(2) == diff
                                    && arr.get(4) - arr.get(3) == diff)
                                return 2;
                            else
                                return 10;
                        } else if (arr.size() == 4) {
                            if (arr.get(3) - arr.get(2) == diff)
                                return 2;
                            else
                                return 10;
                        } else {
                            return 2;
                        }
                    } else {
                        if (arr.size() == 5) {
                            if (arr.get(3) - arr.get(2) == diff
                                    && arr.get(4) - arr.get(3) == diff)
                                return 5;
                            else
                                return 10;
                        } else if (arr.size() == 4) {
                            if (arr.get(3) - arr.get(2) == diff)
                                return 5;
                            else
                                return 10;
                        } else {
                            return 5;
                        }
                    }
                }
            }
        }
        return 0;
    }
}

[spdkimo]

183461 PI spdkimo java 2.8KB 정답 391ms 7분 전 183451 PI spdkimo java 2.9KB 시간초과 50분 전 183450 PI spdkimo java 3.0KB 시간초과 52분 전 183443 PI spdkimo java 10.4KB 시간초과 1시간 전 183442 PI spdkimo java 10.4KB 시간초과 1시간 전 183439 PI spdkimo java 8.5KB 시간초과 2시간 전 183009 PI spdkimo java 8.0KB 오답 246ms 3일 전 너무 안돼서 답을 매우 많이 참고했음

import java.util.Scanner;

public class Main {
    private static final int INFINITE = Integer.MAX_VALUE / 2;
    private static final boolean MY_DEBUG = false;
    private static final int MAX_LENGTH = 10002;

    public static class Solve {
        private String question;
        private int difficulty[];
        private int questionLength;
        public Solve(String sequence) {
            this.question = sequence; 
            questionLength = sequence.length();
            difficulty = new int[MAX_LENGTH];

            int solution = calculationDifficulty(0);
            System.out.println(solution);
        }

        private int calculationDifficulty(int i) {
            if (i == questionLength) return 0;
            int ret = difficulty[i];
            if (ret != 0) {
                if (MY_DEBUG) System.out.println("Cache hit");
                return ret;
            }
            ret = INFINITE;
            for (int L = 3; L <= 5; ++L) {
                if (i + L <= questionLength) {
                    ret = Math.min(ret, calculationDifficulty(i + L) + evaluate(i, i + L - 1));
                    difficulty[i] = ret;
                }
            }
            if (MY_DEBUG) System.out.println("RET: " + ret);
            return ret;

        }

        private int evaluate(int start, int end) {
            final String M = question.substring(start, end+1);
            if (MY_DEBUG) System.out.println( "EVAL " + M);

            char N = M.charAt(0);
            int length = M.length();
            StringBuilder identicalString = new StringBuilder();
            for (int i = 0; i < length; i++) {
                identicalString.append(N);
            }
            if (M.equals(identicalString.toString())) {
                return 1;
            }

            boolean progressive = true;
            for (int i = 0; i < M.length() - 1; ++i) {
                if (M.charAt(i+1) - M.charAt(i) != M.charAt(1) - M.charAt(0))
                    progressive = false;
            }
            if (progressive && Math.abs(M.charAt(1)-M.charAt(0)) == 1) {
                return 2;
            }
            boolean alternating = true;
            for (int i = 0; i < M.length(); i++)
                if (M.charAt(i) != M.charAt(i%2))
                    alternating = false;
            if (alternating) return 4;
            if (progressive) return 5;

            return 10;

        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt();
        while(cases-- > 0) {
            String sequence = sc.next();
            new Solve(sequence);
        }
        sc.close();
    }

}

[Sprexatura]

오우- 이 문제 난이도가 높아서(..'하'인데...) 걱정했는데 두 분 모두 감사합니다 :) 다음에는 문제를 좀 풀어보는 척이라도 하고 뽑아오겠습니다 ㅠㅠ 푸신 분들은 다음에 짧게 설명해주시면 좋을 것 같네요. (에러 난건 아직 해결 못하셨나요??)

[Sprexatura]

휴 저도 결국 에러 해결 못하고 일단 올립니다 ㅠㅠ

RTE (nonzero return code) 에러가 나네요-

알아보니 일부로 자세한 정보는 안주는 것 같습니다.

제자리에서는 잘 동작하는 것 같은데요.. ㅠ_ㅠ(뭘까요)

183913 풀이며 다음과 같습니다 -> difficulty 얻는 부분을 짧게 수정했습니다. 해당 내용은 알고스팟에 안올리고 우선 여기에만 수정한 코드 올립니다.

def getDifficulty(inputString):
    if len(inputString) < 3: return 10
    gap = int(inputString[0]) - int(inputString[1])
    if checkSameGap(inputString, gap):
        if 0 == gap: return 1
        if -1 == gap or 1 == gap: return 2
        return 5
    else:
        if checkSameGap(inputString[0:][::2], 0) and checkSameGap(inputString[1:][::2], 0): return 4
    return 10

def checkSameGap(charList, gap):
    idx = 0
    while len(charList)-1 > idx:
        if int(charList[idx]) + gap != int(charList[idx+1]): return False
        idx = idx + 1
    return True

_dic = {}
def solve(inputString):
    if inputString in _dic:
        return _dic[inputString]
    if len(inputString) <= 5:
        _dic[inputString] = getDifficulty(inputString)
        return _dic[inputString]
    minScore = -1
    for pos in [3,4,5]:
        score = solve(inputString[:pos]) + solve(inputString[pos:])
        if minScore < 0:
            minScore = score
            _dic[inputString] = score
        elif minScore > score:
            minScore = score
            _dic[inputString] = score
        else:
            continue;
    _dic[inputString] = minScore
    return minScore

NumberOfTestcase = int(raw_input())
answerList = []
TestcaseNumber = 0
while NumberOfTestcase > TestcaseNumber:
    lineInput = raw_input().strip()
    answerList.append(solve(lineInput))
    TestcaseNumber = TestcaseNumber+1
    _dic = {}
for result in answerList: print result

solve만 보시면 될 것 같습니다. 풀고 답보니 얼추 비슷하게 했네요