늒네 기록

1439번: 뒤집기 (acmicpc.net) 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 0으로 묶이는 그룹 개수와 1로 묶이는 그룹 개수 중 작은 것을 취하면 되는 문제. 혹은, 0, 1로 묶이는 그룹 개수를 전부 센 다음 2로 나누어서 정수 부분만 취하면 되는 문제. 두 그룹의 수가 같을 경우 2로 나누면 되고, 둘 중 하나가 한 개 더 많은 경우, 즉, 한 그룹은 k개, 한 그룹은 k+1개인 경우 [(2k+1)/2] = k이므로 이렇게 풀어도 답이 나온다. x='';r=-1;(2+require('fs..

1946번: 신입 사원 (acmicpc.net) 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 처음에 LIS 문제인줄 알았는데 다시 보니 스탈린 정렬 문제였다. 두 성적 중 하나로 먼저 내림차순 정렬한 다음, 남은 성적으로 스탈린 정렬 해버리면 끝난다. 즉, O(n)짜리 그리디 문제. a=(0+require('fs').readFileSync(0)).split` ` p=1 while(a[0]--){ b=+a[p] q=r=0 a.slice(p+1,p+b+1).map(j=>j.split` `..

10610번: 30 (acmicpc.net) 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 주어진 문자열에 나온 숫자들을 내림차순으로 정렬한 다음 이 숫자가 30으로 나뉘어 떨어지는지 확인하면 되는 문제. 이렇게 풀리는 이유는 내림차순으로 정렬하면 맨 끝에 0이 온다. 이걸로 10의 배수를 만들 수 있다. 각 자리 숫자들을 전부 더했을때 3의 배수라면 이 숫자들을 어떻게 배열하더라도 3의 배수가 된다. 주어진 숫자들로 가장 큰 숫자를 만든다면 이게 위에서 만든 숫자. 그리디. 가장 큰 숫자가 30으로 나뉘어 떨..

13305번: 주유소 (acmicpc.net) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 중간에 이전 도시보다 기름 값이 높은 도시가 나타나면 제거해버리는 아이디어! 실제 구현은 기름값을 이전 도시들 중 최소 기름값으로 통일하는 식으로 했다. 난이도 기여에 스탈린 정렬이라는 것이 언급되어 있어서 찾아봤더니 드립처럼 존재하는 것이었다 ㅋㅋㅋㅋ gustavo-depaula/stalin-sort: Add a stalin sort algorithm in any language you like ❣️ ..

10162번: 전자레인지 (acmicpc.net) 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 아주 기본적인 그리디 문제다. n=require('fs').readFileSync(0) a='';[300,60,10].map(e=>{a+=~~(n/e)+' ';n%=e}) console.log(n?-1:a)

27646번: Judicious cuts (Easy) (acmicpc.net) 27646번: Judicious cuts (Easy) In the first sample, there is just one line, and that always divides plane into 2 regions. In the second sample, two intersecting lines divide plane into four quadrants. The solution shown for the third case is not optimal, and hence it would not be accept www.acmicpc.net 선을 최대 1000개 그어서 평면을 n개의 영역으로 나누려고 한다면, y = mx + b 꼴..

15610번: Abbey Courtyard (acmicpc.net) 15610번: Abbey Courtyard Bath’s annual Christmas market runs from the 23rd of November 2017 until the 10th of December 2017. During this time, the market will occupy the entire square courtyard of Bath Abbey. To brighten things up at night, a single long strand of cheerful festi www.acmicpc.net 면적이 인풋으로 주어지고, 이 면적을 가지는 정사각형의 둘레를 구하는 문제. 한 변의 길이가 면적의 제곱근이므로 이 ..

14264번: 정육각형과 삼각형 (acmicpc.net) 14264번: 정육각형과 삼각형 첫째 줄에 정육각형 한 변의 길이 L이 주어진다. (1 ≤ L ≤ 1,000,000, L은 정수) www.acmicpc.net 글 작성 시점에 브3으로 난이도가 책정되어있고, 테스트 케이스를 보고 패턴을 유추해서 답을 찾아내는 것이 불가능하지 않기도 하지만, 문제를 증명해서 직접 풀겠다고 생각하면 브3은 아닌것 같다. 위와 같이, 정육각형을 대각선들로 나누는 경우의 수를 전부 찾은 뒤, 각 경우마다 가장 면적이 작은 삼각형을 찾고, 이 삼각형의 크기가 가장 큰 경우를 찾아야 정석적인 풀이가 된다. 모든 경우에서 가장 작은 삼각형의 면적은 정육각형의 한 변과 같은 길이로 만든 정삼각형의 면적과 같다는 사실을 포착해낼 ..

10569번: 다면체 (acmicpc.net) 10569번: 다면체 수학자가 구를 깎아서 볼록다면체를 만들었다. 이 수학자는 임의의 볼록다면체에 대해 (꼭짓점의 수) - (모서리의 수) + (면의 수) = 2가 성립한다는 것을 알고 있다. 그래서 구를 깎는 게 취미인 www.acmicpc.net 기하학 태그가 걸려있어서 들어갔는데 실제로는 사칙연산만 할 줄 알면 되는 문제. 내용은 오일러 다면체 정리를 다루고 있지만, 문제는 v - e + f = 2라는 식에서 v, e값이 주어져있을때 f값을 구하는 것으로, 특별히 기하에 대한 이해가 필요하지는 않다. 인풋으로 주어지는 값에서 첫 번째로 등장하는 숫자를 제거하고 마지막 줄에 등장하는 빈 라인을 처리하는 것만 신경써주면 다음과 같이 풀 수 있다. [,.....

28113번: 정보섬의 대중교통 (acmicpc.net) 28113번: 정보섬의 대중교통 버스에 더 먼저 탑승할 수 있으면 Bus, 지하철에 더 먼저 탑승할 수 있으면 Subway, 버스와 지하철에 탑승하게 되는 시간이 동일하면 Anything을 출력한다. www.acmicpc.net 문제 자체는 어렵지 않다. 지하철을 타러 가다가 지하철이 출발하면 어떡하지- 하는 걱정을 할 수도 있지만, 문제 조건상 그럴 일은 없다는 것을 알 수 있으며, 이렇게 되면 단순히 두 숫자를 비교하는 문제로 바뀐다. 숏코딩을 노려보자! 두 숫자만 받으면 된다. 삼항연산자를 잘 활용해보자. 삼항연산자 문서에 아래와 같은 내용이 있다. 조건 (삼항) 연산자 - JavaScript | MDN (mozilla.org) 조건 (삼항)..