JMK no matter what

역주행중. 옛날에 2등했던 셋. 역시 하드는 못풀음 ... ㅠ 아이디어는 생각해 보면 단순한데. 일단 leave 들을 몽땅 지울 수 있다고 생각한 것이 문제였다. -.-; medium 은 당시에 c&p 신공 레코드였는데.. 그냥 짜봤는데 점수가 비교적 잘 나왔다. 호홍! hashCode() 랑 equals() 짜주는거 대단히 편하다. 'ㅅ'

250 PouringWater

lang:java
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import java.math.*;
import java.util.*; 

public class PouringWater {
    public int getMinBottles(int N, int K) {
        int oN = N;
        while(Integer.bitCount(N) > K) ++N;
        return N - oN;
    }
}

500 PalindromePhrases

대회 당시 C++ 코드

lang:java
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import java.math.*;
import java.util.*; 

public class PalindromePhrases {
    private class State {
        int used;
        String[] residue;

        private State(int used, String[] residue) {
            this.used = used;
            this.residue = residue;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            State state = (State) o;

            if (used != state.used) return false;
            if (!Arrays.equals(residue, state.residue)) return false;

            return true;
        }

        @Override
        public int hashCode() {
            int result = used;
            result = 31 * result + (residue != null ? Arrays.hashCode(residue) : 0);
            return result;
        }
    }
    private HashMap<State,Long> m;
    private String[] w;

    private boolean isPalindrome(String s) {
        if(s == null) return true;
        for(int i = 0; i < s.length() - 1 - i; ++i)
            if(s.charAt(i) != s.charAt(s.length() - 1 - i))
                return false;
        return true;
    }
    private String[] nextResidue(String a, String b) {
        int am = a.length(), bm = b.length();
        for(int i = 0; i < min(am, bm); ++i) {
            if(a.charAt(i) != b.charAt(bm-i-1))
                return null;
        }
        String[] ret = new String[2];
        if(am > bm) {
            ret[0] = a.substring(bm);
            ret[1] = null;
        }
        else {
            ret[0] = null;
            ret[1] = b.substring(0, bm - am);
        }
        return ret;
    }
    private long solve(int used, String[] residue) {
        State here = new State(used, residue);
        if(m.containsKey(here)) return m.get(here);
        long ret = 0;
        if(isPalindrome(residue[0]) && isPalindrome(residue[1])) ++ret;
        for(int use = 0; use < w.length; ++use) {
            if((used & (1 << use)) == 0)
            {
                String[] next = null;
                if(residue[0] == null) {
                    next = nextResidue(w[use], residue[1]);
                }
                else {
                    next = nextResidue(residue[0], w[use]);
                }
                if(next != null) {
                    ret += solve(used | (1<<use), next);
                }
            }
        }

        m.put(here, ret);
        return ret;
    }
    public long getAmount(String[] words) {
        m = new HashMap<State,Long>();
        w = words;
        String[] res = new String[2];
        res[0] = "";
        return solve(0, res)-1;
    }
}