컴퓨터공부하기

0이면 콩이 심어진 상태, 1이면 콩이 없는 상태이다.

배열에 모두 콩을 심어놓고, 배열을 탐색하면서 거리가 2인곳에 위치한 콩을 제거해준다.

그냥 주어진 조건대로 배열을 세로로 접근해서 출력하면 된다.

이때, 쓰레기값이나 '\n'이 저장되어있으면 PASS하면 된다.

() 이렇게 괄호 열고 닫는 문자가 바로 붙어서 나오는 경우는 레이저다.

그러므로 '('를 입력받으면 먼저 막대로 파악하고 개수를 카운트해준다.

입력에서 이전에 '('를 입력받았고, 그다음 ')'을 입력받으면 레이저로 판단하고, 현재 막대 개수만큼 조각을 카운트 해준다. ( 이전에 '('입력으로 카운트 해준 값이 막대기가 아니고 레이저 입력이므로 하나 빼줘야한다)

vector를 이용하여 동적으로 배열을 생성한 후, 과제를 제출한 사람을 따로 체크한다.

앞에서부터 체크가 안된 번호를 출력

이진 탐색을 이용해서 문제를 해결했다.

최대로 걸릴 수 있는시간은 주어진 심사대 중 가장 오래 걸리는 심사대 * 사람수 가 최악의 경우가 된다.

물론 심사대가 2개 이상이면 이시간 까지는 안걸리겠지만, 1개일 때도 고려하면 위 시간이 최악의 경우다.

이 시간을 기준으로 시간을 1/2 씩 탐색해가며, 모든 사람이 심사를 받고 시간도 만족하면 끝

모든사람이 심사를 못받았으면, 시간이 더 필요하므로 오른쪽 탐색

주어진 사람보다 더 많은 사람을 심사할 수 있으면, 시간이 남으므로 왼쪽 탐색하게 된다.

수학의 세계는 신기하다는 것을 다시 한번 느끼게 해준 문제이다.

이 문제는 주어진 문자열을 재구성하여, 재구성한 문자열의 부분 문자열중 팰린드롬의 수가 최대일 때, 몇개인지를 계산하는 문제이다.

주어진 abcabc는 abccba로 재구성하면 a, b, c, c, b, a, cc, bccb, abccba로 9개가 나온다.

이 뿐만 아니라 acbbca, cbaabc등으로도 재구성 할 수 있다.

처음에는 문자열 길이가 최대 10글자이니 모든 문자열을 재구성해서 구현해보았더니 당연히 시간초과이다.

신기한건 문자 a가 10개로 구성된 aaaaaaaaaa은 답이 금방 나오는데 abvcfascdf 이렇게 문자가 섞이면 답이 나오는데 오래 걸렸다.

그래서 다른사람들은 어떻게 해결했는지 찾아보았는데, 이 문제의 경우의 수를 따져서 해결했다.

앞서 abccba는 여러가지 방법으로 최대 9개가 나왔다. 이중 aabbcc 이렇게 같은 문자열을 순서대로 배치했을 때, a, a, b, b, c, c, aa, bb, cc로 똑같이 최대 9개의 팰린드롬 부분 문자열을 가지게 된다.

(뭔가 수학적으로 증명해야 할 것 같지만.. 정확한 증명은 다른 고수분들이 해주실 것이다)

그러므로 각 알파벳을 이용하여 만드는 부분 팰린드롬을 계산해주면 PASS를 받을 수 있다.

인턴을 보내지 않고 최대로 만들 수 있는 팀을 먼저 계산한다.

팀을 하나씩 줄이며, 보내야 하는 인턴수를 만족하면, 그때의 팀이 최대로 만들 수 있는 팀이 된다.

STL을 이용하면 쉽다.

주어진 문자열의 부분문자열은 set에 저장하면, 알아서 다 정렬이 되어있다.

카드를 섞다보면, 나중에는 처음 상태에서 중복되는 섞는 행위를 한다.

중복을 줄이기 위해 m번 수행하고 나면, 진행해야 하는 횟수 k를 m으로 나눠 남은 만큼만 더 수행하면 최종 카드 상태가 나온다.

문제에서 소수 p를 4로 나눈 나머지가 1이면 p= a^2+b^2 을 만족한다고 나와있다.

그러므로 먼저 소수를 계산한 다음, 주어진 범위 내에서 4로 나눈 나머지가 1인 소수를 찾는다.