je_record

문제 바둑판의 상태가 주어지면 흰색 또는 검은색 중 무슨색이 이겼는지 판단 https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 조건 바둑판의 크기는 19 * 19 같은 색의 바둑알이 연속적으로 5알이 놓이면 이긴다. 6알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다! -> 놓치기 쉬움 입출력 입력 바둑판이 19 * 19로 숫자로 표시된다. 검은 바둑알: 1, 흰 바둑알: 2, 알이 놓이지 않는 자리: 0 출력 승부가 결정이 나는 경우 검정 바..

알고리즘 그리디 알고리즘 정렬 풀이 나무 중 자라는 길이가 큰 것을 가장 나중에 자르도록 한다. 첫날 나무의 길이에 매일 자라는 길이만큼 더해지므로, 정수 ans 변수에 첫날 나무의 길이를 다 더해둔 후 매일 자라는 길이 * 자르기 전까지 자라난 일 수를 반복문을 통해 더해준다. 매일 자라는 길이는 오름차순 정렬 후 배열의 끝에서부터 사용하였다. 시간 초과 코드 grow 배열을 정렬하지 않고 굳이 max 값을 일일이 구하여 O(n^2) 시간복잡도가 되어 시간초과 발생 #include #include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "..

알고리즘 그리디 알고리즘 풀이 0번째 스위치를 누르는 경우와 0번째 스위치를 누르지 않는 경우를 나누어 생각한다. 1~n-1번째 스위치를 누를지 말지 여부를 결정하기 위해 for문을 돌린다. i번째 스위치를 누를지 말지를 결정하기 위해 i-1번째 전구의 상태와 목표로 하는 i-1번째 전구의 상태를 비교한다. 같으면 누르고 cnt++ 다르면 누르지 않는다. 현재 전구의 상태와 목표로 하는 전구의 상태가 같으면 cnt를 리턴하고 그렇지 않으면 2147000000을 리턴한다. 0번째 스위치를 누르는 경우와 0번째 스위치를 누르지 않는 경우 중 최소값을 골라 출력한다. 만약에 두 경우 모두 답이 나오지 않아 리턴값이 2147000000인 경우 -1을 출력한다. 전체 코드 #include #include usin..

알고리즘 다이나믹 프로그래밍 풀이 계단 별 점수를 저장하는 벡터 s와 계단 점수의 최대값을 저장하는 벡터 dy를 사용하였다. s[i] = i층 계단의 점수, dy[i] = i층 계단까지의 최대값 dy[1]=s[1] dy[2]=s[1]+s[2] dy[3]=s[3]+(s[1]과 s[2] 중 큰 값) dy[i]=s[i]+(dy[i-2]와 dy[i-3]+s[i-1] 중 큰 값) (n>3) s[i]+dy[i-2] (i 계단의 점수) + (i - 2 계단까지 가는 최대값) s[i]+dy[i-3]+s[i-1] (i 계단의 점수) + (i - 3계단까지 가는 최대값) + (i - 1 계단의 점수) 성공 코드 #include using namespace std; int main() { // freopen("input.t..

알고리즘 다이나믹 프로그래밍 풀이 h 2차원 벡터를 두어 똑같은 색이 이웃하지 않도록 h[i-1]의 값 중 최소 값을 이용하여 값을 누적해간다. 즉, h[i][1]은 i번째 집을 빨간색으로 칠할 때의 최소 비용, h[i][2]은 i번째 집을 초록색으로 칠할 때의 최소 비용, h[i][1]은 i번째 집을 파란색으로 칠할 때의 최소 비용이 된다. 그러면 h[n][1], h[n][2], h[n][3] 중 최소값이 답이 된다. 성공 코드 #include using namespace std; int main() { // freopen("input.txt", "rt", stdin); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, r,..

알고리즘 다이나믹 프로그래밍 풀이 타일은 | 또는 ㅡ 같은 모양을 가진다. 직사각형 2*n에서 n이 하나 증가하면 열이 한칸 더 생기는 것으로 | 만큼이 더 생기게 된다. 그러므로 2*n-1을 채우는 방법에 | 을 붙여주면 된다. 이 외의 경우의 수가 하나 더있는데 = 가로 두개가 마지막에 붙는 경우이다. 이 경우에는 2*n-2을 채우는 방법에 = 을 붙여주면 된다. 즉 직사각형 2*n을 채우는 방법의 수는 2*n-1을 채우는 방법의 수 + 2*n-2을 채우는 방법의 수가 된다. 벡터 dy를 이용하여 나타낼 수 있다. dy[1]은 | 로 채울 수 있는 방법이 하나이므로 1으로 초기화 dy[2]는 || 또는 = 로 채울 수 있는 방법이 두가지이므로 2로 초기화 한다. dy[1]=1 dy[2]=2 dy[n]..