famous명

풀이

정말 고등학교 1년만 제대로 다니면 누구나 풀 수 있는 몇 안 되는 문제가 아닐까싶다.

소스 코드

풀이

r[j] + ds[r[j]]>=r[i+1]

이 코드가 핵심이다. 현재위치 + 사정거리 가 다음 위치보다 짧이지는 순간이 존재한다면 바로 영창을 보내면 되는 문제다. 물론 같은 위치에 있는 사람들중 제일 잘 던지는 사람이 던지는 걸로 말이다.(여기서 해싱 사용)

소스 코드

풀이

이것은 dp로! 이건 처음에 설정을 잘해줘야 하는데, 첫 경우를 S, E, B를 타고 접근한게 아니라면 처음부터 생기는 경우만 존재(1)하고 타고 접근했다면 지금까지 왔던거에 1을 더함(이동하는 경우)으로 설정한다. 그 뒤부터는 알맞게 점화식을 세우면 된다.

소스코드

풀이

요즘 DP문제가 너무 재밌네요ㅋㅋ 이 문제는 입력받는 배열이랑 dp 배열을 만들고 min함수를 만든다음에 현재 i번째에서의 최소는 i-1번째에서 이번과 겹치치 않는 부분중 최소와의 합이다. 라는 생각으로 코딩하면 쉽게 풀립니다. 자세한 건 말보다는 코드로!

소스코드

풀이

미로찾기와 비슷한 알고리즘으로 풉니다. 재귀함수를 이용할 때 주의할 점은 Recursive case(언젠가는 수렴해야 하는 지점)를 잘 설정해야 한다는 것이고요. 동서남북으로 말이 이동할 수 있다고 했으니 s(p+1,q) - 남 , s(p,q+1) - 동, s(p-1,q) - 북, s(p,q-1) - 서 이렇게 방향을 설정해서 재귀호출합니다. 근데 여기서 한 가지 의문이 들 수 있겠네요. 길을 잘 못 들면? 어떻게 최댓값을 구하지? 초기화는 어떻게? 각 장소마다 값을 저장할 수 있는 지점이 있어야 하지 않을까?' 그 해답을 저는 지역변수를 만들자!'라는 생각에서 얻었습니다. 지역변수는 중괄호 블록내에서만 메모리 공간이 할당되기때문에 재귀호출한 함수안에서의 메모리 영역에 값과 그 이전 함수에 메모리 영역에 값에는 다른 값들이 저장되게 됩니다. 그러면 다시 돌아오는 과정이 간편하고 더 이상 동서남북 어느 곳에도 이동할 수 있는 길이 없을 때, 최댓값인지만 비교해주면 문제가 깔끔히 해결됩니다.

소스 코드

풀이

컴퓨터는 원 순열을 표현할 수 없으니 직순열로 바꿔 문제를 해결합니다. vector를 사용하여 m번째 사람을 출력함과 동시에 순열에서 제거 시킵니다. 인덱스 번호는 런타임 에러가 발생하지 않도록 벡터의 사이즈로 나눈 나머지를 유지합니다.

{ j = (j + k - 1) % v.size() }

소스 코드

풀이

이 문제는 일반적인 방법으로는 풀 수 없습니다. 왜냐하면 n이 10만까지여서 이중 for문을 쓰면 시간 초과가 뜹니다. 단일 for문으로 이 문제를 풀려면 식을 따로 만들어야 하는 데 2,3,4,5를 입력 받았다고 가정했을 때, 2*3 + 2*4 + 2*5 + 3*4 + 3*5 + 4*5 이므로 공통인수를 뽑아 인수분해하면 2(3+4+5)+3(4+5)+4*5 입니다. 여기서 발견할 수 있는 규칙은 시그마 k번째 수 * (시그마 k+1번째 ~ n번째 수) 입니다. 이렇게 식을 세워서 계산하면 쉽게 풀립니다.

소스 코드

풀이

단순구현 문제이다.

소스 코드

풀이

c++에서 지원하는 알고리즘 자료구조를 받아와서 key값을 string, value값을 int로 하는 map을 구현합니다. 그러면 map을 인덱스 값이 string, 그 안에 값이 int인 배열처럼 쓸 수 있습니다. map과 배열의 차이점은 map은 값을 넣어줄 때 정렬이 된다는 점입니다. 그리고 string을 사용하면 iostream을 받아와야 되고 scanf(), gets(),printf()를 사용할 수 없습니다. 이 점에 주의하면 시간 초과없이 간결하게 코드를 짤 수 있습니다.

소스 코드

풀이

이 문제는 map을 써도 간단히 풀리지만 더 간단히 푸는 방법이 있습니다. 바로 XOR 연산을 이용하는 건데요. XOR 연산은 다르면 1, 같으면 0을 반환하는 연산입니다. 먼저 XOR의 몇가지 규칙을 알아보자면 1. 0 ^ a = a, 2. a^a = 0, 3. a^b^a^b = 0, 4. a^b^a^b^c = c 입니다. 문자열의 각 문자는 다 아스키 코드 값을 가지게 됩니다. 아스키 코드값을 이진수로 변환해서 비트 연산하면 결국 마지막에는 이름이 호명되지 않은 사람의 이름만이 남게 됩니다.

소스 코드