글 읽기 - 정답 판정 범위에 대해서 질문드립니다.

chldntjr1211 5년 전 0

우선 이 문제의 답은 주어진 N에 대해 유일하지 않습니다.

N=2 일 떄만 해도 1 2 3//1 3 2// 3 1 2// 3 2 1 로 여러가지가 나옵니다.

제가 찾아낸 규칙은 각 레벨당의 노드 수만큼의 연속된 수 집합을 적절히 배열하면 답을 찾을 수 있다는 겁니다.

N = 3 일 떄 1 2 5 7 3 4 6

N = 4 일 떄 1 2 5 10 14 7 8 12 3 4 11 15 6 9 13 역시도 답이 됩니다.

http://hsin.hr/coci/archive/20... 에 방문해 솔루션코드를 찾아봤는데 제 방식과 달라

혹시 모를 노파심에 위 방식이 정답으로 채점되는지 질문드립니다.

package backjoon;

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

public class Main {
    static int[] tree;
    static List<List<Node>> ll;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int treeSize = (int)Math.pow(2,n)-1;
        tree = new int[treeSize+1];

        if(n == 1) {
            System.out.println("1"); return;
        }else if(n == 2){
            System.out.println("1 2 3"); return;
        }

        //초기화
        tree[1] = 1;
        tree[2] = 2;tree[3] = 3;

        ll = new ArrayList<>();
        for (int i = 0; i <= n; i++) ll.add(new ArrayList<>());
        ll.get(1).add(new Node(1,1));
        ll.get(2).add(new Node(2,2)); ll.get(2).add(new Node(3,3));
        Collections.sort(ll.get(2));

        for (int i = 3; i <= n; i++) {
            int[] nextLeftElements = getLeftNodeArr(i);
            int differ = (int)Math.pow(2,i-2);
            for (int j = 0; j < ll.get(i-1).size(); j++) {
                Node node = ll.get(i-1).get(j);
                int nextLeftPos = node.pos*2; int nextRightPos = node.pos*2+1;
                tree[nextLeftPos] = nextLeftElements[j];
                tree[nextRightPos] = nextLeftElements[j]+differ;
                ll.get(i).add(new Node(nextLeftPos,tree[nextLeftPos]));
                ll.get(i).add(new Node(nextRightPos,  tree[nextRightPos]));
            }
            Collections.sort(ll.get(i));
        }
//        System.out.println(Arrays.toString(tree));
//        System.out.println(ll);
        travelPreOrder(1);
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb.toString());
    }

    //레벨이 주어질 때 (1~n) 해당 레벨 왼쪽 노드에 들어갈 숫자 배열 리턴
    /*
        필요한 숫자원소
        n이 3이라면 2^2 , 2^2+1
    */
    public static int[] getLeftNodeArr(int level){
        int arrSize = (int)Math.pow(2,level-2);
        int[] ret = new int[arrSize];
        int adder = (int)Math.pow(2,level-1);
        for (int i = 0; i < arrSize; i++) {
            ret[i] = adder; adder++;
        }
        return ret;
    }
    public static void travelPreOrder(int root) {
        if(root >= tree.length) return;

        sb.append(tree[root]+" ");
        travelPreOrder(root*2);
        travelPreOrder(root*2+1);
    }
}
class Node implements Comparable<Node>{
    int val, pos;
    public Node(int pos, int val) {
        this.val = val;
        this.pos = pos;
    }

    @Override
    public int compareTo(Node o) {
        if(val < o.val) return 1;
        else return -1;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", pos=" + pos +
                '}';
    }
}

chogahui05 5년 전 1

스페셜 저지는 어떤 방식이든 상관 없이.

출력한 것에 대해서 조건에 맞으면 정답 처리됩니다.

Ex. 약수의 갯수가 2개인 수 하나를 출력하세요.

출력

chldntjr1211 5년 전 0

그럼 스페셜 저지 문제의 경우

동일한 조건의 복수의 답을 처리 못할 가능성은 없다는 말인가요?

(제 코드를 맹신하고 서버가 틀렸다는 취지가 아닙니다. 정말 궁금해서 물어보는 겁니다.)

djm03178 5년 전 1

스페셜 저지도 사람이 짜기 때문에 실수할 수는 있지만, 보통의 문제와 같이 의심부터 할 필요는 없습니다.

doju 5년 전 1

글에서 제시하신 N = 4의 경우 답이 될 수 없습니다.

2 + 5 + 10 + 14 + 7 + 8 + 12 = 58
3 + 4 + 11 + 15 + 6 + 9 + 13 = 61

chldntjr1211 5년 전 0

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

정답 판정 범위에 대해서 질문드립니다.

chldntjr1211 5년 전 0

chogahui05 5년 전 1

chldntjr1211 5년 전 0

djm03178 5년 전 1

doju 5년 전 1

chldntjr1211 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말