본문 바로가기

Programming/Solutions

 (52)
[BAEKJOON] 1010번 다리가 겹치면 안 되므로 동쪽에서 뽑은 $M$개의 사이트 순서는 이미 정해져 있는 셈이다. 즉 $M$개 중에 $N$개를 뽑고 순서를 배열하지 않는 것이다. 따라서 $_MC_N = \frac{M(M-1)(M-2) \cdots (M-N+1)}{N!}$을 계산하면 된다. ..까지는 어렵지 않게 알 수 있다. 문제는 자료형의 한계다. Python같은 경우 그냥 분자 계산하고 분모 계산해서 나누면 그만이지만 C의 경우 자료형을 벗어나는 경우가 생긴다. $_{30}C_{15}$의 경우 $\frac{30\times29\times \cdots \times 16}{15!}$를 계산해야 하는데, 이 때 분자값은 $3,042,648,073,975,910,400,000$로 8바이트 자료형의 범위를 한참 벗어난다. 따라서 하나..
[BAEKJOON] 1004번 결국 최대한 원 안에 들어가지 않고 출발점에서 도착점으로 갈 때 몇 개에 원을 지나야 하는지, 즉 지나지 않고는 도착점에 갈 수 없는 원만 지날 때 그 원의 수가 몇 개인지 구하는 문제다. 무조건 지나야만 하는 원은 어떤 것이 있을까? 경로의 길이에는 제한이 없으므로 얼마든지 우회할 수 있다. 우회할 수 없는 원은 딱 두 가지다. ① 출발점을 둘러싸는 원 ② 도착점을 둘러싸는 원 점을 둘러싸는 원 안에 진입하지 않고는 절대 도착점에 도달할 수 없으므로 최소한으로 지나는 원의 수는 이런 원의 수가 된다. 따라서 원이 주어질 때마다 출발점이나 도착점이 그 원 안에 있는지 검사하면 된다. 이 때 출발점과 도착점을 모두 둘러싸는 원은 포함되지 않는다. 이런 원은 우회할 수도 없고 그럴 필요도 없기 때문이다. 출..
[Project Euler] Problem 022 여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일 names.txt 이 있습니다 (우클릭해서 다운로드 받으세요). 이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다. 먼저 모든 이름을 알파벳 순으로 정렬합니다. 각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 수(A=1, B=2, ..., Z=26)를 모두 더합니다. 여기에 이 이름의 순번을 곱합니다. 예를 들어 "COLIN"의 경우, 알파벳에 해당하는 수는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다. names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까? 1 2 3 4 5 6 7 8 9 10 1..
[Project Euler] Problem 026 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import java.util.List; import java.util.ArrayList; public class P026 { public static void main(String args[]) { System.out.print(run()); } public static String run() { int remainder; int max = -1, ans = 2; for(int d = 2; d
[Project Euler] Coding Quiz 2 https://euler.synap.co.kr/quiz=2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 import java.io.BufferedWriter; import java.io.FileReader; import java.util.List; import java.util.ArrayList; public class Q002 { public static void main(String args[]) { System.out.println(run()); } p..
[Project Euler] Problem 005 이미 푼 문제다.(https://t0pli.tistory.com/49) 근데 풀고 1년 정도 지나서 다시 봤더니 뭔 말인지 하나도 모르겠어서 그냥 다시 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import java.math.BigInteger; import java.util.List; import java.util.ArrayList; public class Q005 { public static void main(String[] args) { System.out.println(run()); } public static String run() { List list = new ArrayList(0); for(long i = 1L;..
[Project Euler] Coding Quiz 4 1억 번째 컬럼명만 구하라길래 입력은 따로 안 받았음. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class Q004 { public static void main(String args[]) { System.out.println(run()); } public static String run() { int n = 100000000; StringBuilder sb = new StringBuilder(); sb.append((char)('A' + (((26 + ((n%26) - 1)))%26))); while((n /= 26) > 26) { sb.append((char)('A' + (((26 + ((n%26) - 1)))%26))); } sb.append((char)('..
[Project Euler] Coding Quiz 1 출처가 사이냅소프트 채용퀴즈라길래 뭐하는 데인가 했더니 이 사이트를 운영하는 회사였다. 사이트 첫 페이지(https://euler.synap.co.kr/)에서 확인할 수 있다. 원래는 SW 회사인 것 같고 이 문제를 당사 채용 문제로 출제한 모양이다. 아무튼 나는 이 문제의 더 어려운 버전인 92번 문제를 푼 뒤에 이 문제를 풀었기 때문에 쉽게 풀 거라고 생각했다. 하지만 어림도 없지 ㅋㅋ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 public class Main { public static void main(String args[]) { System.out.println(run()..

티스토리툴바