올빼미 개발자

https://www.acmicpc.net/problem/6064 브루트 포스를 이용하여 문제를 해결해보았다. 전에 풀었던 문제와 비슷하지만 다른점은 유효하지 않은 답에 한해서는 -1을 반환한다는것이므로 while문을 사용하여 처리하면 오류가 발생한다. for을 이용하여 범위를 정해주어야 하는데 어떤경우에 유효하지 않은지 살펴보자 m, n, x, y가 각각 10 12 7 2일때 유효하지 않다. 이유는 x와 y모두 짝수 이기때문에 60갑자와 비슷한 경우인데 갑오년은 가능하지만 갑미년은 없는 이유라고 볼 수 있다. 둘다 짝수 이거나 둘다 홀수일 때 가능하고 하나가 홀수 이고 하나가 짝수인경우는 불가능하다. 이를 파악하기 위해서 카잉 달력의 마지막 해를 알아야하는데 이 카잉달력의 마지막 해라고 한다. 그렇다면..

https://www.acmicpc.net/problem/14500 브루트 포스를 이용하여 해결한 문제. 우선 n ,m값을 받아오고 점수를 저장하는 a[i]값을 받아온다. 각 블럭별로 점수를 계산하여 가장 큰값을 출력해야 하는데 우선 블럭의 갯수부터 생각해보았다. 0000블럭은 가로 세로로 두가지 가능하고 0000 블럭은 한가지 경우만 가능하다. 0000 블럭은 회전 방향에 따라 총 4가지 가능하고 뒤집은 다음 다시 또 4가지 총 8가지의 경우의 수가 가능하다. 00  00 블럭은 회전 방향에 따라 총 2가지 가능하고 뒤집은 다음 다시 또 2가지 총 4가지의 경우의 수가 가능하다.   0000 블럭은 회전 방향에 따라 총 4가지 가능하다. 따라서 모두 합치면 총 19가지의 경우에 블럭의 모양이 가능하고 ..

https://www.acmicpc.net/problem/1107 리모컨을 움직여 주어진 채널로 옮길때 최소 경우의 수를 구하는 문제이다. 우선 숫자를 지웠을때 목표 채널까지 어떻게 하면 가장 가깝게 갈수 있을지 생각해봐야한다. 1. 지워진 숫자를 제외하고 가장 가까운 위치를 찾아야한다. 1-1. 그후 도착하지 못하는 위치라면 +, - 버튼을 이용하여 움직인다. 2. +, - 버튼을 이용하여 움직인다. 브루트포스로 이 문제를 해결하였는데 0부터 500000까지 이동하는 경우의 수를 전부 계산하여 넣어준 뒤, 그 중 가장 가까운 결과만 남기는 방식으로 해결하였다. 하지만 n의 범위가 500000까지라고 해서 거기까지만 반복한다면 답을 못맞추는 경우가 있다. 예를들어 n = 500000일때, 사용가능한 숫자..

https://www.acmicpc.net/problem/1476 준규가 사는 이상한 나라의 계산법에 따르면 1년을 1 1 1이라 부르는데 각각 E, S, M이라 부르고 범위는 다음과 같다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 범위가 넘어가면 1로 치환되는데 이를 이용하여 몇년인지 세는 문제이다. 입력으로 ESM 세 숫자가 들어오고 출력으로는 우리나라의 날짜계산법으로 년도를 출력하면 된다. 맞을때까지 1씩 그냥 증가 시켜보기로 하였다. 일치하지 않는다면 또 1을 증가시키고 1을 증가시키는 중 각각의 최대값에 도달하면 1로 바꿔주는 식을 짜보자. #include #include using namespace std;int E, S, M, Y = 1;int main(int arg..

https://www.acmicpc.net/problem/3085 이것도 브루트 포스로 푸는 문제이다. 단순히 바꾸고 구하고를 반복해보자. 사탕의 색은 char a[51][51]로 선언해주고 이중 for문을 통해 값을 받아온다. swap이라는 함수를 통해 두개의 색을 바꿔줄 수있도록 하였다. 바꾸고 나서 가로행과 세로행의 가장 긴 이어지는 갯수를 세어주었는데, 가로행 바꾸기와 세로행 바꾸기 똑같이 써야해서 check라는 함수로 만들어주었다.  쓰는 변수를 지역변수에서 전역변수로 바꿔주고 가로행검사, 세로행 검사 각각 따로 진행하고 그 중 가장 긴 이어지는 값을 max1에 저장해 주었다. 코드는 다음과 같다. #include #include using namespace std; char a[51][51];..

https://www.acmicpc.net/problem/2309 브루트 포스 첫문제이다. 브루트 포스란 발생할 수 있는 모든 경우의 수를 무식하게 전부 탐색하는 알고리즘을 의미한다.  이 문제에서는 아홉명의 난쟁이의 키를 입력 받은 뒤 오름차순으로 정렬하고 모든 경우의 수를 처음부터 검사해주었다.  검사 방법은 맨 처음은 1234567을 더하여 100인지 검사하고 그뒤엔 1234568 검사하고, 1234569검사하고 아니라면 1234578검사하고 쭉 3456789까지 검사하여 주었다. 연산 횟수는 난쟁이에서 제외할 두명을 아홉명중에 뽑는 경우의 수 * 7이므로 9C2 *7 = 36*7 = 252밬에 연산횟수가 적다. 이 브루트 포스의 장점은 모든 경우의 수를 다 검사하기 때문에 무조건 정답이 나온다는 ..

https://www.acmicpc.net/problem/2133 dp로 해결할 수 있는 문제 n = 1일때는 0이다. n = 2 일때는 3이다. 아래 그림을 숫자로 표현하자면 (12, 34, 56), (13, 24, 56), (12, 35, 46)이다.123456 n = 3 일때는 0이다. 왜냐면 기본 블럭은 2개씩인데 n이 홀수 일때는 다 채울 수 없고 하나가 남기 때문이다.123456789 따라서 n = 짝수 일때의 경우의 수를 구해보면 되는데 4일때도 한번 보자123456789101112 경우의 수가 생각보다 많다. 어떻게 계산해야할까 n = 2 일때 경우의 수가 하나더 옆에 있으니까 단순하게 3 * 3을 해서 구할 수 있을것같지만 23블럭이 하나로 합치는 경우도 생각해야한다. 그렇다면 1 x 2..

https://www.acmicpc.net/problem/13398 지난번 연속합과 달리 연속되는 수열 중 하나를 빼도 되는 조건이 붙었다. 연속합의 최대값을 구하는 방법은 dp를 이용하면 되는데 dp[100001], a[100001]을 int형으로 선언해주고, dp[i]는 i번째 수열로 끝나는 연속합의 최대값이다.  dp[0] = a[0]; for (int i = 1;i  코드로는 이렇다. 하지만 여기서 하나를 뺄 수 있다면 더 커질 수 있는 수열이 어떤것인지 찾아야한다. 하나를 빼는 경우와 안빼는 경우의 dp배열을 두가지 선언해 주고 그 중 더 큰값을 저장해주는 방법을 사용했다. #include #include #define MAX 100001using namespace std;int dp[MAX][..

https://www.acmicpc.net/problem/11054 증가하는 부분 수열, 감소하는 부분수열이 아닌 가장 긴 바이토닉 부분 수열이다. 이전 증가하는 부분 수열이나 감소하는 부분수열의 경우 dp를 통해서 dp[i]까지 가장 긴 부분수열의 길이를 저장해주고 비교하여 풀었었는데 이번에도 똑같이 설정은 해주자. 수열을 담을 a[1001]을 선언해준뒤 이번에는 dp를 이차원으로 선언해준다. 그 이유는 dp[i][0]에는 증가하는 부분수열, dp[i][1]에는 감소하는 부분수열을 담고 그 합에서 -1을 하여 답을 구하려 하기 때문이다. -1을 해주는 이유는 겹치는 수 하나를 빼고 계산해야하기 때문이다. #include #include #define MAX 1001using namespace std;i..

https://www.acmicpc.net/problem/11722 가장 긴 감소하는 부분 수열 가장 긴 증가하는 부분 수열을 반대로 하면 되지 않을까 한다.  윈리는 dp[1001]과 수열을 담을 a[1001]을 선언한 뒤 dp[i]는 i번째 원소로 끝나는 부분 수열 중 가장 긴 감소하는 부분수열의 길이를 저장한다.  그러기 위해서는 일단 dp[i]는 1로 모두 초기화해주고 (항상 자기 자신을 포함하는 수열은 길이가 1이기 때문) i-1부터 0까지 반복하는 for문을 통해 a[j]값이 a[i]값보다 큰 경우에 dp[i]는 기존값과 dp[j] + 1값중 더 큰값을 저장하게 된다.이렇게 a[0]까지 찾은 뒤 dp[i]가 확정되었으면 max값과 비교하여 가장 큰값(가장 긴 수열)을 저장해준뒤 마지막에 리턴해..