PostAddsense


Inchworm Topcoder



public class Inchworm {
    public int gcd(int a, int b) {
        return b==0 ? a : gcd(b,a%b);
    }

    int lcm(int a, int b) {
        return a*b / gcd(a,b);
    }

    public int lunchtime(int branch, int rest, int leaf) {
        return branch/lcm(rest,leaf) + 1;
    }
}


Explanation

처음에는 for문을 이용해 i값에 계속 leaf를 더한 후, i%rest == 0 이면 결과값을 올리는 방식을 사용했다. 여기서 생각해낸 더 효율적인 방식은 최소공배수(least common multiple)를 사용하는 것이었다. rest와 leaf가 첫번째로 같은 수가 바로 최소공배수이고, 이 값을 branch로 나누면 애벌레(worm)가 나뭇잎(leaf)을 몇 개 먹었는지 알 수 있다. 출발 지점에서 하나 먹고 시작하기 때문에 결과값에 +1을 해준다.