맛있는감귤

문제 : https://www.acmicpc.net/problem/2346 github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2346.cpp deque를 이용해 원형 큐처럼 풀었다. 풍선을 터뜨리고 나온 수만 큼 이동하고 해당 수 전까지의 풍선은 다시 push하고 타겟 풍선은 pop만 했다. #include #include using namespace std; deque q; pairp; int N; int main(){ cin>>N; for(int i=1;i>a; q.push_back(make_pair(i, a)); } int pos=0, target, a; p = q.front(); q.pop_front(); cout target){ p = q..

문제 : https://www.acmicpc.net/problem/2302github: https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2302.cpp출처Olympiad > 한국정보올림피아드 > KOI 2005 > 초등부 3번갓초등부의 DP(다이나믹 프로그래밍)문제다이 문제를 자세히 들여다보면 고정석을 기준으로 좌석 수에 따른 경우의 수가 피보나치 수열을 이룬다는 것을 볼 수 있다. #include using namespace std; long cases[41]={0,}; long ans=1; void fibo(){ cases[0]=1; cases[1]=1; for(int i=2;i

문제 : https://www.acmicpc.net/problem/2292github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2292.cpp출처 ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2004 B번규칙 찾으면 쉽게 풀 수 있는 문제이다.중심을 1층이라고 했을 때 다음 층 마지막 번호인 7, 다음 층 번호 19.. 37 ... 로 증가하는 것을 알 수있다.1 7 19 37... 을 보면 An과 A(n-1)의 차가 6의 배수인 계차 수열을 이룬다. #include..

문제 : https://www.acmicpc.net/problem/2206 github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2206.cpp BFS를 이용한 미로찾기에서 벽을 부수는 스킬이 추가되었다. 종종 벽을 부순다거나 폭탄이 주어진다거나 하는 문제 유형이 있는데 그 중의 기본 문제이다. 내 해결 방법은 방문체크(isVisited)배열을 한 차원 더 늘려 벽을 부쉈을 때, 안 부쉈을 때를 나눠 탐색했다. 더 좋은 해결 방법이 있으면 댓글 남겨주시면 감사하겠습니다. #include #include using namespace std; struct Pos{ int x,y,bomb; }; int N,M,dis=1,ans=0; char map[1001..

문제 : https://www.acmicpc.net/problem/2178 github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2178.cpp 지극히 기본적인 BFS 문제 #include #include using namespace std; int N,M,ans=1; queue q; char map[102][102]; bool isVisited[102][102]; int px[4]={1,-1,0,0}; int py[4]={0,0,1,-1}; int main(){ cin>>N>>M; for(int i=0; i>map[i]; pair s; s.first=0, s.second=0; isVisited[s.first][s.second]=true; q.push..

문제 : https://www.acmicpc.net/problem/1966github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/1966.cpp출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 F번ACM-ICPC Live ArchivePKU Judge OnlineTJU Online JudgeSphere Online JudgeHDU Online Judge 입력값이 작아 부르트 포스로 풀 수 있을 것 같지만 디큐를 이용해서 풀어보았다. #include #include using namespace std; int main(){ int T; cin>>T; w..

문제 : https://www.acmicpc.net/problem/1965 DP(다이나믹 프로그래밍)으로 해결가능하다. 이런 문제를 최장 증가 수열 (LIS, Longest Increasing Subsequence) 이라고도 한다. 웬만한 크기가 작은 LIS문제는 아래의 코드로 다 해결이 가능하다LIS O(N^2)의 시간복잡도의 코드 for(int i=0;i

문제 : https://www.acmicpc.net/problem/1932 출처 Olympiad > International Olympiad in Informatics > IOI 1994 1번PKU Judge OnlineSphere Online JudgeDP(다이나믹 프로그래밍)로 해결했다. 삼각형 꼭대기 값을 아래 행에 더해주며 최대값을 저장해 마지막에 출력한다. #include #include using namespace std; int N ,max_sum=0;; int num[505][505]; int sum[505][505]={0,}; int main(){ scanf("%d",&N); scanf("%d",&num[0][0]); sum[0][0] = num[0][0]; max_sum = 0; for..

문제 : https://www.acmicpc.net/problem/1924 기준 날짜부터 주어진 날짜까지 일 수를 다 더한후 7의 나머지 값에 따라 요일 출력 #include int main() { int a, b; int cal[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; scanf("%d %d",&a, &b); int day=0; for(int i=0; i

문제 : https://www.acmicpc.net/problem/1922최소 스패닝 트리 문제이다.프림 알고리즘으로 해결 #include #define INF 1000000001 int N, M; int com[1002][1002]; int dist[1002]; int isVisited[1002]; int sum=0; void input(){ scanf("%d %d",&N, &M); for(int i=1;i