SLENDER ANKLES's 개발블로그

문제정리)

1900년부터 1900 + n - 1년 12월 31일까지의 매월 13일의 요일 분포를 {토,일,월,화,수,목,금}으로 출력하는 문제이다.

1900년 1월 1일은 월요일이다.

윤년을 고려해서 답을 구해야한다. 

문제풀이)

처음에는 어떤식으로 접근해야 하나 고민했다. 

맨처음은 년, 월, 일을 다차원배열로 표현해야 하나? 생각했는데 13일의 요일분포를 구하는데는 적절하지 않는 방법이라고 생각.

그 다음은 전체일수를 하나의 배열로 표현하여 각 날짜들을 count하는 방법으로 생각했다. 

이 방법이 옳은 방법이라고 생각했다. 

년 -> 월 -> 일 을 1차원 배열의 날짜로 표현하기 위해서는 

3중 for문으로 표현하되 각 월과 일의 조건을 몇 개 넣어주면 되겠다고 생각했다. 

그리고 결과적으로 구해야하는 요일 분포를 현재까지의 결과 일수에서 % 7 하면

0은 월요일, 1은 화요일, 2는 수요일, 3은 목요일, 4는 금요일, 5는 토요일, 6은 일요일로

표현가능하여 요일분포배열에 담아서 구현했다. 

윤년을 구하는 방법은 인터넷을 통해서 정확하게 이해했다. 

4로 나누어지는 년도, 100으로 나누어지는 곳은 윤년 아님, 그러나 400으로 나누어지면 윤년

이 조건을 if문으로 적당히 걸어주어서 윤년정보를 적용시켰다. 

다차원 배열을 다루는 부분이 쉬운 줄 알았는데 의외로 조금 시간이 걸렸다.

더군다나 마지막에 엄청난 오류를 범해서 틀린 것이 있었다. 

이 문제는 다차원배열을 이해하고 활용하는데 아주 좋은 문제이기 때문에 몇 번이고 다시 풀어볼 필요가 있을 것 같다.

문제정리)

5 * 5배열에서 어망을 투하해서 가장 많은 수확을 할 수 있는 범위와 그 값을 구하는 문제였다. 

문제풀이)

우선 5*5배열이기 때문에 어림잡아 5 * 5 * 5 * 5 * 5 * 5 이하의 순회를 하게 되는데 , 

15625번? 물론 이 것보다 훨씬 적게 반복문을 수행하는데, 어쨋든 1억번까지 수행하지 않으므로 1초안에 무조건 해결 가능하다. 그렇기 때문에 완전탐색으로 풀면 된다. 

배열의 인덱스 x, y에 접근하게 되면 그 점을 기준으로 오른쪽으로 아래쪽으로 사각형을 모두 만들어보면서 답을 구했다. 

1번째 for문과 2번째 for문으로 사각형의 범위를 잡고

3번째 for문과 4번째 for문으로 영역에 속하는 합을 구했다. 

사각형의 범위는 

세로는 1부터 ~ 6 - 현재점x   까지의 범위를 

가로는 1부터 ~ 6 - 현재점y   까지의 범위를 잡았다.

그 안에 속한 사각형의 어획량을 계산하는 부분에서는

현재점부터 어획량의 범위까지의 길이까지를 반복문을 통해 잡아주었다. 

이 것은 말로 설명하기보다 몇 번이고 다시 풀어보면서 머리속으로 정리해주어야 하는 것 같다.

또 하나 나를 애먹인건 

정사각형과 직사각형의 차이였다.

중고등학교 때 잘못된 지식을 가지고 있어서 애를 먹었다. 

-직사각형은 4각이 90도이고 마주보는 한쌍의 길이가 같은 사각형이다. 

-정사각형은 4각이 90도이고 마주보는 두쌍의 길이가 모두 같은 사각형이다.

직사각형은 무조건 마주보는 한쌍의 길이만 같아야 되는 줄 알았다. 

인터넷을 찾아보니 직사각형은 정사각형에 포함되는 사각형이란다. 

처음에 방향을 잘 못 잡아서 다소 몇 시간 헤맸다.

실전에서 이런 문제를 만나도 잘 풀기위해서는 어떤식의 사고 방식을 가져야 할지 모르겠다.

가로 * 세로 크기의 크기의 색종이에 

가로, 세로 마다 줄이 쳐져 있고, (배열이라는 소리)

자르는 인덱스가 주어진다. 

자르는 색종이들중의 크기 중 가장 최대의 것을 찾는 문제이다. 

문제풀이)

처음에는 장애물을 주어지고 dfs를 수행 할려고 했다. 세 시간을 생각해보아도 명확하게 코딩 할 수 있는 방법이

떠오르지 않았다. 

사각형의 넓이에 범위에 대해서 부분, 부분 나눌 수 있는 방법에 대 해서 생각 해보았다. 

좋은 아이디어가 발견됐다. 

예제를 통해서 설명하면

가로 10, 세로 8

가로 커팅이 2, 3번째 선이라고 입력으로 들어 오고,

세로 커팅이 4번째 선이라고 입력으로 들어온다면,

잘린 세로의 선들을 나열하면 0~2까지 선, 2~3까지의 선, 3~8까지의 선 이렇게 3개다.

잘린 가로의 선들을 나열하면 0~4까지 선, 4~10까지의 선 이렇게 2개다.

이 모든 선들을 가로 * 세로 구하면 모든 사각형의 넓이를 구할 수 있게 되는 것이다.

즉!

결국 잘린 선 중에 가로의 최대 길이,

세로의 최대 길이를 구해서 둘이 곱해주면 최대값을 구할 수 있다는 것이다.

간단하게 생각해서 각각의 사각형의 가로 세로 길이를 구해서 넓이를 구하려고 하다보면 내가 푼 아이디어까지 도달할 수 있게 된다.

문제정리)

스위치개수와 현재 스위치 상태가 입력

학생수가 입력되고 

각 학생마다 학생성별, 학생번호가 입력됨

남자와 같은 경우에는 

학생번호의 배수의 인덱스를 가지는 스위치를 상태 전환

여자와 같은 경우에는

학생번호를 기준으로 좌우 대칭 되는 최대 범위만큼 스위치를 상태 전환

문제 풀이)

남학생은 반복문 수행하면서 자신의 인덱스로 나누어서 나머지가 0이면 그러니까 나누어 떨어지는 인덱스를

상태 변환시켜주면 된다. (i % 학생번호 == 0)

여학생이 조금 당황 스러웠는데,

좌우 대칭의 범위를 count변수로 관리하면서 하나씩 늘려나가면서 대칭되면 while문을 계속 수행하게 했고, 

대칭 되지 않으면 while문을 빠져나오게했다.

한 가지 예외는 범위를 늘리다가 할당된 배열의 범위를 넘어서는 경우가 있을 것이라고 판단했다. 

좌우대칭범위를 설정하는데, (count가 학생번호보다 커지면) 배열 인덱스가 음수가 되기 때문에 종료해야 한다.

count가 (전체 스위치 개수 - 학생번호보다 커지면) 할당된 스위치 개수 이상의 인덱스에 접근하기 때문에 종료해야 한다.

이 부분만 잘 처리해주면 크게 문제 없이 수행하는 코드가 완성

문제가 길다고 어려운 것은 아니다. 차근차근 읽어보고 해결책을 찾아보면

대개 긴 문제들이 오히려 쉬울 가능성이 높다는 것을 느낀다.

악보 (1<=N<=10000)개, 각 악 보당 비트(0<=bi<=120)의 정보가 주어진다. 

처음에는 2차원 배열을 쓰는 문제인가 생각하다가 

손으로 그려보면서 풀어보니 1차원 배열로 푸는 것이 답을 구하는데 더 좋다고 판단했다. 

1차원 배열의 범위는 10000 * 120 => 1200000

백이십만개 정도면 된다. 

악보의 비트 정보가 주어지면 

그 해당 배열에 악보넘버를 저장해주는 식으로 입력을 구성했다. 

for(악보범위 i)

while()

       arr[전역변수로 관리하는 인덱스, 곧 시간] = i(악보번호)

로 저장해주면 

ques가 날라왔을 때(시간) 바로 인덱스로 접근해서 답을 도출해내면 된다.