맛있는감귤

문제 : https://www.acmicpc.net/problem/2458 github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2458.cpp 출처 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2011 > 초등부 4번 갓초등부 문제치고는 쉬운 문제다. 플로이드 와샬 알고리즘을 이용해 각 노드의 연결 여부를 판단하고 자신의 키가 몇 번째 인지 아는 학생 (모든 연결고리를 가지고 있는 학생. 즉, 반복문을 돌린 배열에서 본인 노드가 N이라면 (N, Y)와 (X, N)이 모두 true인 노드)의 개수를 출력해주면 된다. 굳이 일일이 연결된 수를 계산안하고 bool 배열로 true 값만 찾아줘도 됩니다. #include #define IN..

문제 : 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