240401-TIL

4월 1일

 

4월의 시작은 알고리즘 문제와 함께

 

오늘 풀어본 문제는 바로

 

기사단원의 무기

이번에 풀어볼 문제는 기사단원의 무기다

 

 

문제 설명을 보니 기사단원의 번호가 정해져있고 

 

기사단원이 들수있는 무기는? 자기 번호의 약수의 개수만큼의 공격력을 가진 무기를 들수가 있다고 한다

 

그런데? 너무 강한 기사단원의 등장을 막기위해 약수의 개수가 limit을 넘어가는 기사단은 패널티를 받아

 

power만큼의 공격력을 가진 무기를 가져야 한다고 한다.

 

우리는 기사단원이 가지는 무기를 만들기 위한 철의 개수를 구해야하는데

 

철의 개수는? 기사단원의 무기 공격력 만큼들어간단다

 

그러니 1~number 까지의 기사단원의 무기의 공격력을 다 더해서 return해주면 문제가 끝나겠지?

 

 

 기사단원이 들수있는 무기의 공격력을 나타내줄 atk 변수를 하나 만들어 줬다

 

 

첫번째 반복문은 1~number까지 돌면서 기사단원을 한명씩 불러들인다

 

두번째 반복문에서는 1~ 현재 기사단원의 번호까지 돌면서 약수를 구한다

 

i % j == 0이라면 j가 기사단원의 번호의 약수니깐 무기 공격력을 1씩 올려준다

 

그런데 무기 공격력을 올려주다? limit보다 크면? atk에는 power만큼의 공격력을 넣어줘서 너무 강한 기사단원의

 

등장을 막아주자

 

 

안쪽의 반복문을 탈출하면 answer에는 무기 공격력을 더해주고 다음 기사단원의 무기공격력을 측정하기 위해

 

atk를 0으로 만들어주자

 

 

반복문을 다 돌아서 빠져나왔다면 기사단의 무기를 만들기위해 차곡차곡 answer에 모아놓은 값을 return해주자

 

 

테스트 성공!

 

이렇게 잘 풀리는줄 알았으나!

 

이렇게 시간이 오래걸려 실패가 뜨는 경우가 있었다.

 

 

아무래도 반복문을 n번만큼 돌고 또 안의 반복문에서 n번만큼 돌기때문에

 

number의 값이 크게 들어오면 완전 오래걸리나보다.....

 

도저히 다른 방법이 생각이 나질 않는다.... 다른 사람에게 도움을 요청해보자!

 

다른사람의 풀이를 가지고 해체 분석해보자

 

일단 배열하나를 만들어준다 배열의 크기는 number+1만큼 만들어주자

 

왜 이렇게 number의 +1만큼 크게 만들어줄까나 고민했었는데 아마

 

 

그 다음 반복문에서 i를 1부터 시작하기 때문이 아닐까 라고 조심스럽게 추측해본다

 

배열의 첫번째 인덱스인 atk[0] 부터 시작하는게 아니라 두번째 인덱스 atk[1]부터 시작하기 때문에?

 

일부러 배열을 number보다 한칸 크게 만들어줘가지고 계산하기 쉽게 만들어 준건가 보다.

 

안쪽 반복문도 나와는 조금 다른데 j의 시작을 i부터 시작해서 number와 같을때까지 돌아준다

 

반복문이 한번돌때마다 j는 i만큼 증가된다. 이 부분이 핵심이다 약수를 구하는 방법을 나와 좀 다르게 구현했다

 

처음 i = 1일때 안쪽 반복문에서 atk[j]는 j가 공평하게 1씩 증가해서 atk[1] ~ atk[number]까지 공평하게 1씩 들어간다

 

그 다음 i = 2일때는 j 에 2가 들어가서 atk[2], atk[4], atk[6].... 이렇게 2로 나누어지는 곳에만 1씩 증가시켜주고

 

그 다음 i = 3 일때 3으로 나누어지는 곳에만 1씩 증가시키는 방식이다 

 

이 방식대로라면 내가 구현한 1 ~ number까지 다 돌면서 약수를 찾아 atk에 1씩 더해주면서 약수를 찾는 방법보다 훨신 효율적으로 약수를 구할수가 있을것이다.

 

이중 반복문을 빠져나오면 다시 한번 반복문을 만나게 된다 이곳에선 atk[1]~ atk[number] 까지를 돌며

 

atk[i]가 limit보다 크다면 answer에 power를 더해주고 아니라면 atk[i]를 더해주면서 

 

기사단원들의 무기를 만들기 위해 필요한 철의 무게를 answer에 넣어주고 있다.

 

 

통과...

 

전체적으로 봤을때 내가 만든 알고리즘보다 훨신 시간도 짧게 걸린다.

 

너무 많은걸 배웠다

오늘은 아마 알고리즘 문제를 풀면서 처음으로 내 손으로 못풀고 다른 사람의 풀이에서 도움을 받아보았다.

 

너무 많은걸 배운 하루였다

 

4월 1일 TIL은 여기서 마치도록 하겠다.