치킨 날다

https://redchiken.tistory.com/136

저번주에 링크와 더불어 문제 해석을 해놓았기에 이전 글 링크로 대체합니다.

오늘은 Fridge of Your Dream 문제를 풀고, Scortched World 문제를 해결하다가 멈추었습니다.

Fridge of Your Dream은 이전에 생각해 놓았던대로 문제를 해결하니까 매우 쉽게 해결이 되었습니다.

그만큼 매우 쉬운 문제였구요.

하지만 Scortched World는 생각해 놓은 식대로 풀이가 되지 않았습니다.

적을 맞추는 궤적은 두가지가 있습니다. 종달속도에 도달하기 전에 맞추는 것과, 그 뒤에 맞추는 것.

하지만 막상 발사하기 전에는 이것이 어떻게 될지 모릅니다.

그러다 보니 종달높이를 이용해 식을 분할하는 방식을 채택할 경우, 같은 작업을 반복해야 합니다.

결국 사용할 수 있는 식이 한정되 버리게 되었습니다.

V를 구해야 하는데 그 와중에 도달 시간 T가 필요합니다.

이 과정에서 식이 매우 복잡해집니다.

우선은 다음주에는 이 문제를 좀 더 시도 했다가, 아니다 싶으면 다른 문제를 풀어보려 합니다.

https://www.acmicpc.net/contest/view/116

오늘 늦잠 잘 정도로 컨디션도 안좋고, 오른쪽 손목이 좋지 않아서 조금만 하려고 했습니다.

하지만 막상 문제를 풀려니까 저번에 풀려고 적어 놓은 문제가 상당히 어려웠습니다.

그래서 남은 시간 문제 해석을 다 해놓고 해결방안이 기억이 난다면 메모를 해놓으려 합니다.

해석 하고 나니까 영어로 된 문제 중 쉬운 문제가 많아 슬펐습니다.

Party

문제

남성 그룹과 여성 그룹이 파티를 갖을 때마다 데이트를 1번 한다.

남성 그룹의 그룹원들이 최소 1번 이상 데이트를 할 때까지 개최되어야 하는 파티의 최소 수를 구해야 한다.만약 파티 횟수와 관계 없이 데이트가 불가능한 남성 그룹원이 발생한다면 impossible을 출력한다.

입력

n

m f

w1 m1 ... mw

.....

wf m1 .... mw

n = 테스트 횟수

m = 파티에 참여하는 남성의 수

f = 파티에 참여하는 여성의 수

w* = *번째 여성이 데이트 하고 싶은 남성의 수

m* = 여성이 데이트 하고 싶은 남성의 순번

출력

모든 남성들이 최소 1번 이상 데이트를 할 수 있는 파티 횟수

횟수와 관계 없이 데이트를 못하는 남성이 있을 경우 impossible 출력

해결방안

1. m*의 값이 0부터 m까지 모두 존재하는지 확인. 없을 경우 impossible

2. 

Save the computer!

문제

한 학기동안 컴퓨터를 맞췄을 때, 학기동안 파산하지 않을 확률을 구해야 한다.

컴퓨터는 여러 부품으로 되어 있는데, 하나라도 망갖기면 컴퓨터가 구동하지 않는다.

남은 돈으로 망가진 부품을 새로 교체 할 수 있다.

i번째 부품이 학기동안 k번 망가질 확률은 e^-a(i) * a(i)^k / k!이다.

a(i) = i번째 부품이 학기동안 망가지는 횟수의 기대값

k = 망가지는 횟수

입력

n

c b

a(0) .... a(c)

p(0) .... p(c)

n = 테스트 횟수

c = 부품 갯수

b = 컴퓨터 부품 구매에 투자 할 수 있는 잔액

a(i) = i번째 부품이 학기동안 망가지는 횟수의 기대값

p(i) = i번째 부품의 가격

출력

파산하지 않는 최고 확률

Fridge of Your Dream

컴퓨터 옆에 설치한 냉장고는 안에 콜라 무게를 LED로 표현한다.

이를 10진수로 변환하여 화면에 표현하자

입력

n

b

n = 테스트 횟수

b = 24자리의 이진수 숫자

출력

입력된 이진수 수를 십진수로 표현

해결방안

1. 2^0에서 2^24까지 값이 저장된 메모리를 생성한다.

2. 입력된 수를 뒤에서부터 문자 하나씩 받아 메모리 값과 곱하여 합산한다.

Scorched Earth

문제

포트리스와 같은 게임으로 적과 자신의 위치, 미사일을 쏘는 각도, 속도, 중력가속도(9.8m/s^2), 바람이 존재한다.

이 때 주어진 조건 하에 어느 속도로 쏴야 적을 맞추는지 연산해야 한다.

입력

n

x1 y1 x2 y2 w d

n = 테스트 횟수

(x1, y1) = 자신의 탱크 위치

(x2, y2) = 상대의 탱크 위치

w = 바람 세기(가속도)

d = 각도

출력

적을 맞출 수 있는 속도 v

제한 된 속도 내로 맞추지 못한다면 impossible을 출력한다.

해결방법

t1 = 포탄이 최대 높이까지 도달하는데 걸리는 시간

t2 = 포탄이 최대 높이에서 적 탱크까지 도달하는데 걸리는 시간

H = 최대 도달 높이

h = 자신의 탱크와 적의 탱크 사이의 높이 차

D = 자신의 탱크와 적의 탱크 사이의 거리 차

Vcos(d)(t1 + t2) + w(t1 + t2)^2 /2 = D 공식이 만족해야 함.

t1 = Vsin(d) / g

t2 = (2(H-h)/g)^0.5

H = (V sin(d))^2 / 2g

Free Willy

단어 두개와 몇가지 조합이 주어진다.

첫번째 단어에서 최소한의 조합을 이용해 두번째 단어를 만드는 횟수를 구하자.

만약 주어진 횟수 안에 불가능하면, whalemeat를 출력하자.

입력

n

N P L

W1 W2

P(0)

...

p(P)

n = 테스트 횟수

N = 단어 길이

P = 조합 갯수

L = 제한 횟수

P(i) = 조합

출력

제한 횟수보다 더 적게 맞출 수 있다면 그 횟수를 출력한다.

만약 불가능하면, whalemeat를 출력한다.

https://www.acmicpc.net/contest/view/116

오늘은 저번에 풀다 만 Virus 문제를 풀고, Party 문제를 해석하였습니다.

Virus 문제에서 고민을 했던 순회, 고립 등의 문제는 발생하지 않았습니다.

조건 상으로도 발생하지 않기도 했지만, 애당초 그런 입력을 주지 않는 것 같습니다.

코드를 제출 한 결과 50% 부분에서 시간초과가 났습니다.

대부분 이 부분에서 문제가 생기는 것 같은데, 몇 가지 시도를 하다가 우선은 보류하였습니다.

Vector를 사용하는 것이 문제가 될거라 생각하지는 않습니다.

동적할당으로 바꾸면 문제 해결에 도움은 될것이지만, 근본적인 알고리즘이 문제일 것이라 생각합니다.

Party는 아싸 컴공 학생들을 간호과 학생과 미팅시켜주는 문제입니다.

컴공과 학생과 간호과 학생을 불러 파티를 개최합니다.

파티 후 간호과 학생들이 선호하는 컴공과 학생 중 한명과 데이트를 합니다.

이 때 최소 몇번의 파티를 개최하면 모든 컴공과 학생들이 최소 1번은 데이트를 하는지 구하는 문제입니다.

단, 파티를 아무리 해도 모든 학생이 데이트를 하는 것이 불가능 하다면 이를 따로 출력해야 합니다.

문제 푸는 방식을 구상하는 것은 다음 주에 할 예정입니다.

https://www.acmicpc.net/contest/view/116

오늘은 저번 주에 풀던 [꿍의 여친 만들기] 문제를 해결하고, [Virus] 문제를 시도했습니다.

[꿍의 여친 만들기]는 여성의 이상형 리스트를 받아 그 중 가장 성취하기 쉬운 매력도에 대한 cost를 구하는 문제입니다.

풀이 자체는 어렵지 않습니다.

이상형들 중 가장 얻기 힘든 매력의 cost들을 비교하여 가장 낮은 것을 출력하면 됩니다.

하지만 입력받은 data를 가공하는 작업이 다른 문제들에 비해 난이도나 양이 조금 높았습니다.

그 부분에서 저번 주에 문제가 있었고, 이번주에도 많은 시간을 낭비하였습니다.

또한 StringStream 초기화 부분에서 문제가 발생하기도 했습니다.

여러 객체를 생성하지 않고 하나의 StringStream 객체를 생성해서 사용하는데, 

StringStream 객체를 clear 하거나 flush 해도 안의 내용이 남아 있었습니다.

이에 대해 해결 방안을 찾다가 다음 블로그에서 해답을 찾았습니다,

http://egloos.zum.com/mcchae/v/11130705

"Clear 함수는 안의 내용을 실질적으로 지우지 않고 rdbuf라는 플래그만 0으로 초기화 한다"는 내용입니다.

이를 해결하기 위해서는 stringstream 안에 담긴 string을 blank string으로 덮어씌워주고,

rdbuf를 초기화 하여 앞에서부터 다시 담을 수 있도록 해야합니다.

오늘 해결하다가 만 [Virus]는 생화학폭탄의 폭파까지 걸리는 시간을 출력하는 문제입니다.

폭탄 안에는 N개의 바이러스가 있고, 각 바이러스는 N개 미만의 바이러스와 1개의 성분을 생성하며 자가분해합니다.

이 중 중성자(정확히는 삼중수소)의 갯수가 한도를 넘어가면 폭탄이 폭파합니다.

이 문제는 입력 받은 데이터를 정리하고, 대략적인 문제 푸는 방식을 세우는 것까지 완료하였습니다.

주어진 바이러스 공식을 하나씩 적용하면서 조건을 맞춰보면 될 것으로 예상합니다.

몇가지 걱정거리가 있다면, 입력된 바이러스의 변이가 일관적이지 못해 한번 정리를 해야 한다는 점.

바이러스 중 발생하지 않는 바이러스가 존재 할 수 있다는 점.

순환 발생 체크나 폭탄이 폭파하지 않는 조건 판단 등.

그리고 영어 문제라서 문제 해석이 느린 점도 앞으로의 개선 사항이라 생각합니다.

문제를 풀면서 독해 능력이 조금은 늘었으면 싶습니다.

링크 : acmicpc.net/contest/view/116

1. 첼시를 도와줘!(해결)

그룹 내 선수 가격과 이름들을 입력받고 가장 가격이 높은 선수 이름을 출력하는 문제.

입력 받으면서 이전 입력된 선수 가격보다 비쌀 경우 저장. 아닐 경우 제거.

최종적으로 저장된 선수 이름 출력.

2. Forgger(미해결)

다른 개구리를 밟고 넘어서야 이동 가능한 개구리가 있다.

발판이 된 개구리는 사라진다.

(X, 0)에 있는 파리를 잡아 먹기 위해 {(x, y) | x <= 0, y는 정수}에 배치되어야 하는 개구리의 수를 구하는 문제.

처음에는 지수함수 형태로 증가하는 줄 알았으나, 오류가 나서 X = 4일 때를 한번 구해보았습니다.

상당히 복잡했으나 그 결과 값을 구했고, 이는 복잡한 계차함수를 나타내고 있었습니다.

식은 대략 diff[index] = Sum[i = 1 to index](diff[index - i] * i)이며

주어진 예시가 0<=X<=31인데 X가 31이면 long long 범위를 넘어서버립니다.

현재 이 마지막 X = 31인 케이스 처리를 앞두고 구현을 멈췄습니다.

3. 꿍의 여자친구(미해결)

상대 여성의 이상형 매력 포인트의 조합으로 받고,

각 매력에 대한 코스트를 계산하여 이상형에 가까워지는데 필요한 최소한의 코스트를 계산하는 문제.

입력받는 데이터를 split으로 분리해야 하는데 이 과정에서 문제가 발생함.

하루에 시간을 정해놓고 문제를 푼 뒤 못 푼 문제는 넘어가는 것보다,
테스트를 하나 정해서 안에 있는 문제를 다 풀고 넘어가려 합니다.

따로 만든 이유는 일지를 쓰는 것이 그날 활동을 빼먹지 않고 계획을 지키는데 큰 도움이 되어서 따로 신설했습니다.

앞으로 매주 수요일에 Online Test 1번, Online Judgement 2~3회 정도 진행을 하려 합니다.

그리고 그날 풀었던 문제 링크와 결과, 대략적인 풀이 방법 등 복기를 이 일지에 적겠습니다.