백준 C++ 2775번 부녀회장이 될테야 ( 2차원 배열, 누적합 )

 

오늘은 저녁에 마라탕을 먹었다.

오랜만에 먹었는데..

맛있었다!

 

리뷰가 무려 11000개여서 먹어보았다.

근데 2.5 정도 시키고 둘이 먹었는데..

양이 좀 애매했다.

뭔가 엄청 엄청 많을 줄 알았는데

그냥 엄청 많았다.

 

그렇다.

맛은 괜찮다.

가끔 먹으면 맛있다.

 

휴!

오늘은 뭔가 바빠서 문제를 후딱 풀고 싶었는데.....

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

문제를 함께 보자..

 

---

 

HA.....

이 문제를 이해하는데 한 시간이 걸렸다.

내 생각 반 지피티가 읊어주는 걸 이해하는데 반..

정말 어지럽다.

첫 번째는 이해했다. 1층 3호에 살려면 0층 123 사람들 수 합만큼 데리고 살아야 하니 6명

아니 근데 도대체 왜 2층 3호는 10명밖에 안 되는 것인가.......

2층 1호부터 머리가 이상해지기 시작했다.

그러면 0층사람들 다.. +1층에 1호..

 

이러면서 이게 10이 나오는 게 나로서 이해가 안 갔다.

 

그렇게 지피티에 힌트를 물어봤다.

 

지피티는 일단

1. 패턴을 찾으세요.

2. 2차원배열로 푸세요.

라고 알려줬다

 

이차원 배열로 A [15][15] 정도로 맞추라고 했고

거기 안에 이제 A [k][n] = i;

를 넣어주는 것이다.

 

그다음에 이제 중요 패턴 1을 작성해야 한다.

 

내가 이 힌트를 보기 전에

누구 더하기 누구는 얘다라고 생각했던 게

밑집 두 개를 더하면 윗집호수가 되나?라고 그냥 스쳐 지나갔는데

꽤 나름 힌트였다.

 

이렇게 패턴을 찾는 게 참 중요하다는 것을 알게 되었다.

 

그래서 지피티를 뜯고 뜯어서

패턴을 알아냈다.

 

2층 1호 / 1명	2층 2호 / 4명	2층 3호 / 10명	2층 4호 / 20명
1층 1호 / 1명	1층 2호 / 3명	1층 3호 / 6명	1층 4호 / 10명
0층 1호 / 1명	0층 2호 / 2명	0층 3호 / 3명	0층 4호 / 4명

 

밑에 집 두 개가 아니라

누적합이라는 사실

 

즉 1층 2호 사람은

0층 1호 + 2 호고

1층 3호 사람은

0층 1호 + 2호 + 3호이다.

 

근데 보면

이게 3명이라 헷갈려서 그렇지 4라고 쳐보자

 

1층 4호 사람이라면

0층 1234호를 다 더하면 10이다

근데 이게 자세히 보면

0층 4호 + 1층 3호인 것과 같다.

왜냐면 1층 3호는 이미 0층 123을 더했기 때문에

0층 4호랑 1층 3호를 더하면 같은 것이다.

4호여서 그렇지 15였으면 1부터 15까지 더하녜 마녜 식이 늘어날 텐데

15면 그냥 14호 + 밑집 15호 인 셈

 

그래서 이것을 식으로 표현하면!

 

A [k][n] = A [k-1][n] + A [k][n-1]

 

이렇게 되는 것!!

 

그리고 가장 중요한 것.

제약조건이 있다.

 

문제에도 적혀있지만

0층은 i호만 큼 사람이 있다. 그래서 0층은 i로 통일해주어야 하며,
패턴상 1호 사람들은 싹 1이다. 왼쪽에 사람이 없기도 하고 
그래서 1호 사람들은 늘 1이라는 것까지 제약을 추가해야 한다.

 

 

난 부녀회장 안 하고 싶다..

이거 푸는데 두 시간 넘게 들었다..

글 쓰는데도 한 시간...

정말 정말 쉽지 않다....ㅋㅋㅋㅋ

 

이전 답을 공개해 달라고요?!

 

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

지피티는 ans필요 없고

규칙도 이상하며

변수이름도 제각각이라며 혼나버렸다.

 

힌트를 왕창 보며 풀었다.

과연 괜찮을까? 싶긴 한데....

이렇게라도 풀었으니 내 역량 한 스푼 들어간 셈 아닐까....?..

...ㅎ

 

부녀회장 안 한다! 선언!