분류 전체보기
-
[백준 1010번] 다리 놓기백준 알고리즘 2019. 3. 3. 21:12
BOJ 1010번 다리놓기 https://www.acmicpc.net/problem/1010백준 1010번 C++ 소스 DP배열을 0으로 초기화할때 memset(DP, 0, sizeof(DP)); 으로 제출했더니 컴파일 에러가나서int DP[33][33] = { 0 }; 이렇게 초기화 했다.i는 N을 컨트롤하는 변수이며, j는 M을 컨트롤 하는 변수이다. 코드 18번째 줄에서 DP[1][i] 를 모두 오른쪽 다리의 개수로 대입한다.i가 1이면 j값에 따라서 경우의 수 값이 결정되기 때문이다. 코드 25번째 줄에서 i가 최소 2부터 시작하므로 j도 최소 2부터 시작한다.입력범위 N, M (0 < N ≤ M < 30)를 참고했을 때 i=2, j=1 이렇게는 시작할 수 없기 때문이다. j가 i보다 항상 같거나..
-
[백준 10844번] 쉬운 계단 수백준 알고리즘 2019. 2. 28. 02:08
BOJ 10844번 쉬운 계단 수https://www.acmicpc.net/problem/10844백준 10844번 C++ 소스 DP배열 index를 0부터 시작해도 되지만 편의상 1자리수 일 때 1로 index를 시작하였기에 DP배열의 범위가 벗어나지 않게 여유롭게 DP[103][13]을 선언했다.변수 i는 현재 자리수를 나타내는 변수이고,변수 j는 0~9까지 루프를 돌게 되는데 첫자리가 아닌 끝자리가 0~9로 적용한 것이다. 끝자리가 0일때는 바로 앞자리에 1만 올 수 있고, 끝자리가 1일땐 바로 앞자리에 0또는 2가 올 수 있다. 끝자리가 9일때는 바로 앞자리에 8만 가능할 것이다. 또한, 실질적 연산은 N이 2이상 입력되었을 때 진행되며, N이 1일때는 solve함수가 실행되지 않는다. N이 2이..
-
[백준 1018번] 체스판 다시 칠하기백준 알고리즘 2019. 2. 25. 03:25
BOJ 1018번https://www.acmicpc.net/problem/1018백준 1018번 C++ 소스 1개열(column) 각각 1개씩 열(column)이 아니라 전체 8X8을 기준으로 놓고 브루트포스 해야한다. white와 black경우의 수 2개를 모두 다 구해봐야함. 예를들어 [0][0]이 B일때 black_check만 할것이 아니라 반드시 white_check도 해봐야 한다는 것.첫 째자리를 W로 바꿨을 때 최적이 될 수 있기 때문이다. 체스판이니까 가로로 B,W,B,W이런식으로 된다는건 쉽게 알 수 있었는데 세로로도 B,W,B,W이렇게 가로처럼 엇갈리게 되야한다는걸 모르고 문제풀어서 꽤나 고생했었다. 변수 i,j는 행(또는 열)을 하나씩 옮겨주는 변수임 ex) [0]~[7]까지 조사가 끝..
-
[백준 1912번] 연속합백준 알고리즘 2019. 2. 25. 03:07
BOJ 1912번 연속합 https://acmicpc.net/problem/1912백준 1912번 C++ 소스 코드설명 long long으로 한 이유는 예를 들어 N이 100000까지 입력이 들어올텐데 만약 100000개가 모두 1000이입력되었다고 가정하면 더하는 과정에서 DP랑 val변수에 오버플로우가 발생할 수 있기 때문이다.arr는 int형으로 하려다가 max() 함수의 특성상 long long과 int가 서로 자료형이 달라서 그런지 아래사진처럼 max함수 수행이 안되어서 그냥 arr도 DP자료형이랑 똑같이 long long으로 선언했다. 이 문제는 DP(동적계획법)로 풀어야한다. DP[i] = max(DP[i - 1] + arr[i], DP[i]); DP[i] = max(DP[i - 1] + a..
-
[백준 2473번] 세 용액백준 알고리즘 2019. 2. 23. 20:06
BOJ 2473번 https://www.acmicpc.net/problem/2473백준 2473번 C++ 소스 브루트포스로 i, j, k 변수 선언하고 3중 for문으로 풀려고 했었으나, 그렇게 되면 N^3 이라 시간초과가 날 수 밖에 없다. https://en.wikipedia.org/wiki/3SUM 에 힌트가 있었다. fix라는 변수를 이용해서 하나를 딱 정한다음에 start와 end를 이용해서 점점 조여오는 방법이다. i) 3개의 수 합이 0보다 클 경우 0에 가깝기 만들기 위해 end를 하나 줄여서 작은수를 대입시킨다. ii) 3개의 수 합이 0보다 작을 경우 0에 가깝기 만들기 위해 start를 하나 늘려서 큰 수를 대입시킨다. iii) i, ii 의 경우에 모두 해당하지 않는 경우는 0이므로..