본문 바로가기

algorithm

14391 종이조각 https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 문제 : n*m직사각형 판을 작은 직사각형 조각으로 자르려고 한다 (이때 직사각형은 1*1칸마다 숫자가 적혀있다) 가로 조각은 왼쪽부터 , 세로 조각은 위에서부터 숫자를 읽어준다. 종이를 적절히 잘라서 조각의 숫자 합의 최대값을 찾아라 해결 : (1 ≤ N, M ≤ 4) N,M이 작다 ----> 브루트포스로 접근해보자 어떤 수에 우리가 도달했을 때 (가로 or 세로 ) 중에 고를 수 있다. 따라.. 더보기
Six Degrees of Kevin Bacon https://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon Six Degrees of Kevin Bacon - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Parlour game on degrees of separation Six Degrees of Kevin Bacon or Bacon's Law is a parlor game where players challenge each other to arbitrarily choose an actor and then connect them en.wikipedia.org Its a game 영화 배우 한 명을 골라서 그 .. 더보기
1018 체스판 다시 칠하기 문제 : 주어진 판을 올바른 체스판으로 만들기 위해서 다시 색을 칠해야하는 칸의 개수의 최솟값을 구하라 해결 : 최솟값 -> 경우가 여러가지가 있는데 그 중에서 최소인 경우를 찾아라 8*8체스판 + 시간 2초나 주어졌다?? -> 브루트포스를 이용해볼까? (사실 이미 분류에서 찾아서 들어온거긴 한데..ㅋ) 색깔이 행마다 반복이 될텐데 (BW + WB) or (WB + BW) 이 두 가지 경우뿐이다. 아 근데 8*8로 잘라서 하라고? n,m ( n,m >= 8) (n - 8 + 1)(m - 8 + 1) 만큼 확인하면 되겠다! 코드: #include using namespace std; char board[100][100]; int checkBoard(int r, int c){ int ans1 = 0, ans.. 더보기
[Codeforces] suffix array https://codeforces.com/edu/course/2/lesson/2/1 Courses - Codeforces codeforces.com [문제] S = ababba SUFFIX ARRAY = { ", a, ba, bba, abba, babba, ababba} 를 정렬하면 {", a, abba, ababba, bba, babba} How to store all these suffixes? What about string array? It will be too much b.c. the total length of the array is n^2 Instead let's store only the index of the first letter of each suffix 위의 예) {6, 5, 2, .. 더보기
[BOJ 9660] 돌 게임 6 문제 : 턴을 돌아가면서 돌을 1개 ,3개, 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 이긴다. 두 사람이 모두 '완벽하게' 게임을 한다. 누가 이기는 가? 상근이가 게임을 먼저 시작한다. 창영이가 다음으로 한다. 돌의 개수는 N개인데 1 ≤ N ≤ 1,000,000,000,000 풀이 방법 : 1개, 3개, 4개 일 때는 한 번에 가져가며 이긴다. 둘 다 돌이 자신의 차례에 1개 , 3개 , 4개가 안 남게 행동을 할 것이다. => 자신의 차례에 2개가 남으면 자신이 이김 https://casterian.net/algo/sprague-grundy.html (여기를 참고함..) The Casterian Home casterian.net N=1 상근 N=2 창영 N=3 상근 N=4 상근 N .. 더보기
[BOJ] 2467용액 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 1. 모든 조합을 모두 살펴보는 것은 nC2만큼의 계산이 필요하다. n이 최대 10만이므로 시간초과가 날 것이다. 2. 답이 될 후보들 추리기 힌트로 오름차순으로 숫자를 주기 때문에, 이분탐색(lower_bound)으로 어떤 숫자 n의 -n과 같거나 큰 숫자를 구하고, 이 숫자의 왼쪽에 있는 숫자, 이 두 개를 비교해서 답을 구하면 될 것이라고 생각했다. 그런데, 이 경우에는 모든 숫자들이 .. 더보기
dp연습1 1. https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 0 1 2 3 4 ... n 1 스티커[1][1] 스티커[2][1] ... ... ... ... 2 스티커[1][2] 스티커[2][2] ... ... ... ... 세로로 쭉 테이블 채우기 dp[i][1] : 2번을 포기 1번 선택했을 때 최댓값 dp[i][2] : 1번을 포기 2번 선택했을 때 최댓값 dp[i][1] = max(dp[i-1][2] + A[i][1], dp[i-1].. 더보기
[BOJ] 3178 코코스 반으로 잘라서 정렬을 한 후, 인접한 두 문자열의 겹치는 접두사의 길이만큼 트라이에서 정점이 감소하는 것이므로 n * k에서 길이만큼을 빼주면 된다 #include #include #include using namespace std; int n,m,k; vector s; vector e; int cmp(string a, string b,string c, string d){ int i = 0, j = 0; if(a == b) i = k; else while(a[i] == b[i]) ++i; if(c == d) j = k; else while(c[j] == d[j]) ++j; return i + j; } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0.. 더보기

티스토리툴바