Buen Camino

2017.11.01 ** 수요일 ** Solution - 1012(유기농배추)
백준 1012 유기농배추

풀이방법: dfs

문제 해석

알고보니 예전에 틀렸던 문제이다, 왜 틀렸을까..

어렵지는 않다.

상하좌우 움직임 / dfs 만 알면된다.

풀이방식

한번 생각해보자 ,

지렁이는 움직인다. 지렁이가 이동하면서 모든 배추를 보호한다.

=> 다시말해서, 1이 모여있는 구역당 지렁이가 한마리면 된다.

상하좌우로 움직인다.

=> x,y가 움직일 두 개의 이동배열을 만든다.

int nx = x + dx[i];

int ny = y + dy[i];

1일때 dfs탐색을 시작한다.

=> map{i}{j}==1이면 탐색을 시작한다. 탐색을 시작할때마다 카운팅한다.

for (int i = 0; i < M ; i++) {

for (int j = 0; j < N ; j++) {

if (mapi == 1&&!visitedi) {

visitedi = true;

dfs(i, j);

cnt++;

}

}

}

방문했던것은 방문하지 않는다. (안하면 스택오버플로우)

=> 각 칸당 boolean 타입의 visited배열을 만들어 방문하면 true바꿔준다.

if (isRange(nx, ny)&& !visitednx&&mapnx==1) {

visitednx = true;

dfs(nx,ny);

}

이게 전부다. 그리고 재귀해주자,

코드 전체 보기

: 예전엔 왜 틀렸을까.. 중간에 10분정도 오류를 못찾았다.. 이유는..예제를 카운팅하면서 6으로 숫자를 세가지고

왜 5가 안되는거지 하면서 고민했다. 맞다 바보다..

2017.11.01 ** 수요일 ** Solution - 11051(이항 계수2)
백준 11051 이항 계수2

풀이방법: 동적계획법

문제 해석

이항 계수 문제이다. 고등학교때 수학을 배웠다면, 쉽게 생각할 수 있다.

단 .. 기억을 하고있다면 ...

역시 나는 기억하지 못하고 있었다(공부는 못해도 수학은 좀 했다 신승범짱!)

네이버 검색을 해서 이항계수의 공식을 보는데 이렇게 풀면 되겠구나 하는게 있었다.

출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98

이 공식을 보고 풀이를 시작했다.

풀이방식

한번 생각해보자 ,
우리는 n과 k를 안다.
두가지로 나눠져있다.

=> 두개의 경우로 나눠서 합치자!

순열,조합을 풀다보면 항상 재귀를 떠올리게 된다.

이것 또한 재귀적 방법으로 풀면된다. 또한 메모이제이션을 통해 효율성을 높여주면된다.

그리고 공식에서는 우측이 n+1이지만, 우리는 굳이 저렇게 할필요없다. 모든 항목을 -1해주자

이제 끝이다. 뽑기만 하면된다.

그리고 베이스 케이스 설계를 해야되는데, 한 번 생각을 해보자, 뽑을때마다 각 케이스 별로 -1씩을 해줄것이다.

dp {n}[k} = solution(n-1,k-1) + solution(n-1,k);

이렇게 식을 세우게 되면 어느순간 k==n 또는 k==0이된다. 수학시간에 배웠다. nCn =1 , nC0 = 1이다.

그러면 우리는 베이스 케이스를 설계 할 수 있다.

if(n==k||k==0) return 1;

이렇게 설계하면 될 것이다.

그리고 메모이제이션

if(dp{n}{k}>0) return dp{n}{k}

이제 끝이다 !

이렇게 3줄이면 끝난다. 검증을 하고 싶다면 예제를 손으로 하면된다. 5분도 안걸린다.
코드 전체 보기

: 나이를 먹더니 수학을 다 까먹은 것 같다..