너와 나의 스토리

문제: www.acmicpc.net/problem/4920 문제 풀이: 위 순으로 각각 2, 2, 4, 4, 1가지 경우의 수가 있다. 각 경우를 vector에 넣어주고, 모든 위치에서 해당 블록들을 놓아 합을 계산했다. 소스 코드: #include #include #include using namespace std; typedef pair P; vector blocks; int n,arr[101][101],caseSize,answer; void init() { vector block; // 1-1 for (int i = 0; i < 4; i++) { block.push_back({ 0,i }); } blocks.push_back(block); block.clear(); //1-2 for (int i =..

문제: www.acmicpc.net/problem/16955 문제는 "구사과의 돌(x)을 하나 더 뒀을 때, 가로/세로/대각선으로 x가 5개 이상 연속하는지"를 찾는 것이다. 문제 풀이: 모든 점에 대해, 그 점에서 오른쪽의 그림과 같이 4방향으로 5칸을 스캔한다. 5칸 안에 'o'가 존재하지 않고, 'x' 4개가 있다면 바로 1을 리턴해주면 된다. 주의! 처음에는 for(int k=0~5)가 끝나고 cnt('x'의 개수)가 4개이면 바로 1을 리턴해줘 계속 틀렸었다 ㅠㅠ 다음과 같은 경우가 발생할 수 있다. 즉, 현재 'x'를 4개 발견해도 다음에 놓을 곳이 바둑판을 넘어갈 수 있다는 사실을 명심하자! 소스 코드: #include #include #include using namespace std; c..

문제: https://www.acmicpc.net/problem/12100 문제 풀이: N이 최대 20이고, 5번만 이동시킨다는 조건이 있기 때문에, 완전 탐색으로 풀 수 있다. 상하좌우, 4방향으로 숫자들을 민다. -> 5번 움직이므로, 경우의 수는 $4^5$ 아래의 코드는, 숫자들을 위로 미는 코드이다. if (dir == 0) { // 위로 for (int i = 0; i < n; i++) {//y int put_idx = -1, cur = -1; for (int j = 0; j < n; j++) {//x if (arr[j][i] == cur) { arr[j][i] = 0; arr[put_idx][i] = cur * 2; cur = -1; res = max(res, arr[put_idx][i]); ..

문제: https://programmers.co.kr/learn/courses/30/lessons/60057 문제 풀이: 주목할 조건: 앞에서부터 반복되는 문자열이어야 한다. 반복되는 문자열의 길이가 같아야 한다. 반복되는 문자열의 길이가 [10,100) 사이의 숫자이면 길이가 2 증가하고 e.g. 11abc. -> 문자열 길이 5 풀이: 문자열의 길이를 1부터 n/2가지 늘려가면서 중복 문자열 개수를 카운트 최대한 길게 겹치는 문자는 절반씩 같은 문자 e.g. abcabc 맨 처음 문자열을 sub라고 두고, 다음부터 보는 문자열을 cnt로 둔다 같으면 cnt++ 아니면 지금까지 겹친 문자열 개수 계산한 다음 cnt=0으로 초기화 소스 코드: int solution(string s) { int len =..

문제: https://www.acmicpc.net/problem/14889 문제 풀이 1: - 재귀 ateam[20], bteam[20] 1~N 번 중 위 두 팀에 속할 선수들을 재귀로 선택 두 팀 모두 인원수가 n/2일 때, 능력치 계산 시간: 20ms 소스 코드: 더보기 #include #include #include #include #include #include #include #define INF 987654321 using namespace std; int n,arr[21][21],ateam[21],bteam[21],res; void func(int at,int bt,int cur) { if (at== n / 2 && bt==n/2) { int asum = 0, bsum = 0; for (in..

문제: https://www.acmicpc.net/problem/16235 문제 풀이: deque로 나무 위치랑 나이 저장 봄 현재 존재 하는 나무 처음부터(나이 어린 나무부터) 보면서 (pop_front()) 자기 나이만큼 양분 먹을 수 있으면 먹고 나이 증가 시켜서 다시 push_back() 못 먹으면 죽음 -> 죽는 나무 위치랑 나이 따로 큐에 저장 여름 위에서 죽은 나무들 큐 빌 때까지 돌리면서 양분 추가 가을 나무 deque 돌리면서 번식 가능한 나무 찾아서 따로 큐에 위치 저장 다 돌렸으면 저장해둔 큐 빌 때까지 돌리면서 번식시킴 새로운 나무는 항상 나이가 1로 가장 어리기 때문에 push_front() 겨울 양분 추가 소스코드: typedef pair P; int n, m, k, bab[11..

문제: https://www.acmicpc.net/problem/14476 문제 풀이: 왼쪽부터 gcd 값 기록하는 배열 하나 오른쪽부터 gcd 값 기록하는 배열 하나 만들기 ex) 입력: 8 12 24 36 48 입력 값 8 12 24 36 48 left to right 8 4 4 4 4 right to left 4 12 12 12 48 만약 arr[0]인 8을 뺀다면 rtol[1]이 최대공약수가 된다. 만약 arr[1]인 12를 뺀다면 gcd(ltor[0],rtol[2])가 최대공약수가 된다. 즉, 해당 위치의 직전 최대공약수와 이후 최대공약수의 최대공약수가 전체의 최대공약수가 된다. ㅎㅎ 소스코드: int n, arr[1000001],ltor[1000001],rtol[1000001],res1,res..

문제: https://www.acmicpc.net/problem/17136 문제 풀이: 격자판에서 1인 부분을 만나면 그 위치에서 붙일 수 있는 가장 큰 색종이부터 붙여 봄 붙인 부분 격자판 0으로 바꿈 붙이다가 붙이려는 색종이를 이미 5장 썼다면 모두 덮는 것 불가능 하므로 리턴 붙인 부분들 다시 1로 바꿈 지금까지 쓴 색종이 수가 이전의 최소 결과보다 크다면 더 볼 필요 없이 리턴 typedef pair P; bool arr[10][10]; int paper[6], res = 25; int measure(int x, int y) { int tmp = 5; for (int i = x; i < 10; i++) { for (int j = y; j < 10; j++) { if (!arr[i][j]) { tm..