목록Algorithm (427)
Mini
[틀림] 백준 17822 원판돌리기 // 구현, 배열회전, 원형 dfs
https://www.acmicpc.net/problem/17822* 틀린풀이인접한것들 지우는 idea (좌우, 상하 1개씩만 비교)반례 : 3단 인접인경우, 처리가 안됨dfs를 해야하나? * 정답풀이원형 dfs에서 next 계산방법else if 주의수정후 else if 안하면 바로 조회하기때문에 오답이됨. else if 써야함. #includeusing namespace std; int n,m,t,ret, vis[54][54];int x,d,k, found;vector v[54];const int dy[] = {-1, 0, 1, 0}; // 상, 우, 하, 좌 (y 방향)const int dx[] = {0, 1, 0, -1};void calc() { for(int i=0;i rotate(..
[틀림] [알고리즘] 백준 2632 피자판매 // 누적합, 원형배열
https://www.acmicpc.net/problem/2632* 풀이1dp로 해보려다 실패 * 풀이2원형을 선형으로 만드는 힘 (뒤에 고대로 붙이면 됨)구간쿼리는 누적합 (누적합은 1-idx로 하는게 편한듯)경우의수는 등장 횟수를 저장하라 start 의 범위 문제start [1,2,3] / 간격2 의 예시에서 막라운드는 [3,1] 이다.막라운드 일때, start index는 4다.4 = n(3) + interval(2) -1 이다. #includeusing namespace std; int n,m,target,ret;int a[2004], b[2004], pa[2004],pb[2004];map ma, mb; // int main(){ ios_base::sync_with_stdio(0); cin..
[틀림] [알고리즘] 백준 15685 드래곤 커브 // 구현, 기하문제는 규칙을 찾아라
https://www.acmicpc.net/problem/15685* 풀이과정시도1너무복잡.. gg * 큰돌풀이상태를 정의함각 그림을 상태(숫자)로 표현!!숫자에서 규칙찾기vector에 [방향][세대] = { 방향정보들 } 저장#includeusing namespace std; int ret;int n,x,y,d,g;vector v[4][11]; //v[방향][세대] : { ... } 방향정보들int dy[] = {0,-1,0,1}; // 오위좌아int dx[] = {1,0,-1,0};int vis[104][104];void go(int x, int y, int d, int g) { int _x = x; int _y = y; vis[y][x]=1; //시작점 체크 // 주의 : 0세대부터 ..
[틀림] [알고리즘] 백준 17825 주사위윷놀이 // 완탐 , 구현, 인접리스트, 백트래킹
https://www.acmicpc.net/problem/17825* 틀린풀이그리디 (틀린풀이)먼저 완탐이 되는지 봤어야함인접리스트 사용안하고 vector 여러개로 구현하다보니 너무 복잡... gg * 정답풀이adj로 2개 연결하는것도 표현값은 v에, index는 adj에 저장 // 값과 index를 분리해서 저장하라.adj.size로 특수이동인지 판별백트래킹으로 모든 경로 확인#includeusing namespace std; const int INF = 987654321;// 게임에 필요한 전역 변수들int a[14]; // 주사위 값을 저장하는 배열int mal[4]; // 4개의 말의 현재 위치를 저장하는 배열int n = 10; // 총 주사위 던지는 횟수int v[104]; /..
[틀림] [알고리즘] 백준 1911 흙길 보수하기 // 라인스위핑
* 풀이핵심 아이디어변수를 잘 정의해야함. idx 변수 : 현재까지 덮은 위치b : 필요한 널빤지 갯수 = 길이 / m + (길이%m)이 있으면 +1 없으면 + 0크게 3가지 경우로 나누기첫경우 -> pass나머지경우 -> 길이를 계산, idx 갱신#includeusing namespace std; void fastIO(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);} int n; // 웅덩이의 개수int m; // 널빤지의 길이int idx; // 현재까지 덮은 위치int ret; // 필요한 널빤지의 총 개수int b; // 현재 웅덩이를 덮는데 필요한 널빤지 개수int main(){ fa..
[알고리즘] 백준 14891 톱니바퀴 // 구현, 배열회전
https://www.acmicpc.net/problem/14891* 내풀이0-idx로 만들기solve함수가 최종본시계, 반시계를 예시를 통해 해보면서 결정vv에 회전대상 {톱니번호, 방향}을 담는게 특징실수한부분 : i를 회전할게아니고 vv[i].first를 회전해야함#includeusing namespace std; vector topni[4]; //topni[0] : {1,0,1,0,1,1,1,1}vector> v; // 명령어들vector> vv; // [{회전대상톱니 idx, 방향}, ... ]int k;void goleft(int cur, int dir) { int nxt=cur-1; if(nxt=4) { return; } if(topni[nxt][6]!=t..
[알고리즘] 백준 3190 뱀 // 덱 bfs, 구현, 뱀-꼬리 문제는 덱
https://www.acmicpc.net/problem/3190 * 풀이1(오답)한방향 (->) 진행만 구현후 회전함면 되는지? 안됨참고 : 시계회전은 a[i][j] = a[j][n-i-1] 임반시계 : [n-j-1][i]각 방향에 따라 dfs 돌기로함예제3에서오답 -> 표 디버깅 -> 회전시 꼬리의 위치갱신이 어려움꼬리가 (1,4) 였는데 바로 (2,4)로 되버림 // (1,5)가 되야 맞음꼬리의 상태를 어떻게해야 저장하지? -> 덱 * 풀이21-idx는 무조건 0-idx로 바꿔서 풀기!visit으로 몸통을 체크할것head가 지나가면서 visit을 기록하는 걸로 생각하면 쉬움.#include using namespace std;int sec,y,x;int n,k,L, a[104][104], vis[1..
[알고리즘] 백준 12100 Easy // 구현, 대칭구현은 한방향만 만들고 배열회전을 이용하라
* 시행착오제발 문제좀 읽자.앞부터 합쳐야 하므로 아래그림은 모두 틀린 풀이이다.그리고 한뱡향만 구현하고 회전을 이용하는게 훨씬낫다.틀린코드(초안)#include using namespace std;typedef long long ll;int ret;int n, a[24][24];void moveup() { for(int j=0;j v; for(int i=n-1;i>=0;--i) { if(a[i][j]==0) { continue; } if(i-1>=0 && a[i][j]==a[i-1][j]) { v.push_back(2*a[i][j]); --i; } else { ..