Backjoon 단계별 문제 풀이 Level 05
in backjoon problem list on Programing Using C Lang, backjoon Level problem
백준 단계별 문제집 레벨5 모든 내용은 Git Hub에도 있습니다.
Level5
Problem.4673
4673번 문제(성공)
셀프넘버
Wiki 참고
Problem.1065
1065번 문제(성공)-한수 각 자리수가 등차 수열을 이루면 한수로 취급한다. 예를 들어 보자 99는 한수 인가? 9와 9는 공차 0으로 한수이다. 그렇다면 100은 어떤가? 한수 일리가 없다. 즉 99이하는 전부 한수가 된다. 하지만 100부터는 각 자리수에 따라 달라질수도 있다. 100이후 첫 한수가 되는것은 111일것이다.
Problem.2448
2448번 문제(성공)-파스칼 삼각형 별찍기 입력 N줄이 주어지고(N은 3*2^K의 수로 보장됨), 최대 열의 갯수는2N-1개가 됨.
N줄의 최대 값은 3072이고, 열의 최대 값은 60143개임
처음에 별이 고정됨. 즉, 이 3줄이 한 셋트임.
그리고 별셋트가 찍히는 규칙이 있는데 이게 바로 파스칼 삼각형에서 홀수인 부분들만 별셋트가 찍히는 것이다.
6줄 기준
1
1 1
1 1
1 3 3 1
1 1
1 5 5 1
위에서 홀수인 부분들만 별 셋트가 그려지게 된다. 몇가지 규칙을 찾을수 있는데, 위에부터 0,0 밑에 줄은
1,0과 1,1 이라고 해보자. 1행에 별이 그려지기 위해선 이전 행의 좌표에 별의 유무가 중요하다.
그럼 다음 2행을 보자.
2행은 2,0 2,1 2,2 이렇게 세개가 존재 하지만 실제는 2,1은 비어 있다. 이항 정리에 의해 2가 되어야 하지만
우리가 만들려는 규칙에서는 짝수는 무시해야 한다. 그럼 이 짝수 부분을 어떻게 무시하면서 별을 그릴까?
바로 이전 행 1행을 살펴 보면 된다. 2,1과 비교해야 하는 행은 1,0 과 1,1이다 둘다 별 셋트가 존재 한다.
그럼 일반화를 시켜볼수있다.
a[i][j]=a[i-1][j-1]^a[i-1][j+1]
//만약 이전 행의 양 쪽의 값이 존재 하거나 양쪽다 값이 없다면 0일 테고,
//양쪽의 값이 다르다면 1일 것이다.
//이는 이전 행에 값이 1개만 존재 해야 함을 알수 있다.
이처럼 2,1의 별셋트를 그리지 않아도 됨을 1행의 0열과 1열의 값을 XOR해서 0이 나오기때문에 2,1의 값은 0으로 채우면 되는것
Tip 잘못된 배열의 값 비교
만약 잘못된 배열의 값을 비교하려고 하면 어떻게 될까? 물론 쓰레기 값이 들어가게 된다.
int a[2][2]={0,};
int i=3,j=4;
if(a[2-i][3-j])
printf("What\n");
결과는 어떨까? 물론 What이 출력된다. 잘못된 값을 참조할 지라도 쓰레기 값이 나오기 떄문에 if문이 성립된다. 하지만 정작 중요한것은 그게 아니다.
배열은 스택에 저장되기때문에 만약 저기처럼
a[-1][-1]을 참조하고자 한다면 a에 대한 배열이후에 저장된 어떠한 주소 값을참조한다는 의미다.
다음 예제를 보면 확실하게 이해할수 있다.
잘못된 배열주소 참조
int arr1[8]={12,},arr2[8]={33,};
printf("arr1[-9]%d arr1[-9]%p arr2[0]%d arr2[0]%p\n",
arr1[a-9],&arr1[a-9],arr2[0],&arr2[0] );
//이런 경우는 어떨까?
//뇌피셜상 잘못된 주소를 참조 하니 쓰레기 값이 나오거나 os혹은 컴파일러에 따라서 에러에 관한 값과 주소를 출력해줄것 같다. 아니면 아예 Segmentfault를 토해낼 꺼다.
근데?!!! arr1[-9]33 arr1[-9]0x7ffee7f938d0 arr2[0]33 arr2[0]0x7ffee7f938d0 자세히 보자 잘못된 주소를 토해내야 하지만 두 값은 정확히 같은 값을 보여준다 왜그럴까? arr1[-9]는 사실상 권장하지 않는 옛 표기법이지만 불가능한것은 아니다. 위에서 같이 arr1[-9]는 arr1의 배열이 4byte*8의 크기로 스택에 저장되어 있을것이다. arr1의 시작 주소는 0x7ffee7f9389E이다 스택은 밑에서 위로 자라나고, 여기서 -9칸 즉, arr1배열의 끝인 0x7ffee7f938cc에서 한칸더 올라간 arr2의 시작 주소를 가르키는 것이다. 그래서 두 값이 일치하게 되는것! 그래도 이런식의 표기는 구조를 복잡하게 만들기 때문에 피해야 할것같다.
그럼 이제 별을 그리는 알고리즘을 확정해야 한다.
*
* *
*****
한상 맨 윗줄의 * 은 N개의 줄이입력 되면 N-1번째에 위치함. 그래서 처음 별 셋트에 대해서 초기값을 정해줘야함.
a[0][n-1]=a[1][n-2]=a[1][n]=a[2][n-3]=a[2][n-2]=a[2][n-1]=a[2][n]=a[2][n+1]=1
00000100000
00001010000
00011111000
00100000100
01010001010
11111011111
이제 판별식을 만들어 줘야한다.
if(i>2)
a[i][h]=(j>2&&a[i-3][j-3])^a[i-3][j+3]
//처음 시작 N-1에 찍힌 별셋트를 시작으로 다음 별을 그려야 한다.
//처음 별이 그려지고 i가 3일때를 생각해 보자
//4번째 줄에서 별이 찍혀야 하는 부분은 j가 2,8에서 별이 찍힌다.
// j=2 => a[3-3][2-3]^a[3-3][2+3] => a[0][-1]^a[0][5] => 쓰레기값^1=1
//a[3][2]=1
// j=8 => a[3-3][8-3]^a[3-3][8+3] => a[0][5]^a[0][11] => 1^쓰레기값=1
//a[3][8]=1
//결국 별이 찍혀야 하는 부분만 1이 저장되고 아닌 부분은 0이 저장되는것
이분 블로그를 참고하고 작성했습니다. http://codersbrunch.blogspot.kr/2016/12/2448-11.html