목록전체 글 (616)

1일1알

백준 25194번 결전의 금요일 C++ (골드5)

https://www.acmicpc.net/problem/25194 주어진 수들을 더하는 경우중에 7로 나누었을때 나머지가 4가 되는 경우가 있으면 목요일에 일을 끝내고 금요일에 헬스장을 갈 수 있다. 결국 나머지를 구하는 문제이기 때문에 주어진 수들을 7로 나눈 나머지들을 저장하여 나머지가 1~6인 경우의 수가 몇개인지로 관리하였다. 만약 7로 나누었을때 나머지가 0이면 더해도 의미가 없는 숫자이기 때문에 제외했다. 그리고 백트래킹을 통해 가능한 경우를 탐색하여 7로 나누었을때 나머지가 4인 경우를 찾았는데, 사실 7로 나누기 전의 숫자들로 백트래킹을 진행하면 숫자의 경우가 최대 1000개이기때문에 시간초과가 난다. 하지만 7로 나눈 나머지를 통해 1~6이 몇개인지로 관리하고 있기 때문에 정렬이 되어있..
알고리즘 2024. 6. 5. 11:24
백준 25556번 포스택 C++ (골드5)

https://www.acmicpc.net/problem/25556 스택에서 뺀 뒤에 뒤에서부터 배치하여 오름차순이 되어야 하기 때문에 스택에 top에는 큰 수가 들어있어야 하고, 작은 수를 되도록 스택에 먼저 넣어야 한다. 만약 스택에 수를 넣을때 스택의 top이 지금 넣을 수보다 크다면 뺄때 오름차순이 불가능하다.그렇기 때문에 스택에 수를 넣을때 스택의 top이 지금 넣을 수보다 작다고 무조건 넣으면 안되고 스택의 top이 지금 넣을 수보다 작은 수중 제일 큰 수를 찾아서 해당 스택에 넣어야 한다. 이렇게 진행하다가 만약 모든 스택의 top이 지금 넣을 수보다 크다면 꺼냈을때 오름차순이 불가능하다.#include #include #include #include #include #include #inc..
알고리즘 2024. 6. 3. 10:33
백준 17953번 디저트 C++ (골드5)

https://www.acmicpc.net/problem/17953 캐시테이블을 cache[디저트 번호][날짜][전과 같은 디저트 여부] 로 만들어서 dp로 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;using int64 = long long;int n, m;vector> v;vector>> cache;int dp(int dessert, int day, int isSameDessert){ int& val = cache[dessert][day..
알고리즘 2024. 6. 2. 12:06
백준 15488번 나이트가 체스판을 벗어나지 않을 확률 C++ (골드5)

https://www.acmicpc.net/problem/15488 dp테이블을 [행][열][움직일 수 있는 횟수]로 정하고 똑같은 행,열, 움직일 수 있는 횟수를 2번이상 탐색한다면 기존에 구해놓은 값을 바로 반환하는 메모이제이션 방식을 사용하였다. 나이트가 다음에 가있을 칸을 계산하고 움직일 수 있는 횟수를 1씩 줄이면서 탐색해나간다.1. 만약 나이트가 체스판 밖에있다면 0을 반환한다.2. 만약 나이트가 방문한 [행][열][움직일 수 있는 횟수] 가 이전에 탐색된 기록이 있다면 그 값을 바로 반환한다.3. 만약 k가 0이면 더이상 움직일 수 없고, 체스판 안쪽에 있기 때문에 1을 반환한다. 나이트가 움직일 수 있는 방향은 8방향이기때문에 8방향에 대해 탐색을 진행한 값을 8로 나누고 캐시 테이블에 저..
알고리즘 2024. 6. 1. 11:06
백준 1930번 정사면체 C++ (골드4)

https://www.acmicpc.net/problem/1930 a,b,c,d순으로, 역삼각형 모양의 전개도로 입력이 들어왔다고 가정하면a가 밑면일때 b,c,d가 시계방향으로 배치되어있고b가 밑면일때 a,d,cc가 밑면일때 d,a,bd가 밑면일때 c,b,a로 배치되어있다. 위의 경우들은 전부 같은 모양이다.위의 경우들을 저장해놓는다. 뒤에 들어오는 4개의 입력중 첫 입력은 밑면이고, 위에서 저장해놓은 밑면들과 비교하여 만약 밑면이 같다면 나머지 3개의 입력을 비교하여 같은지를 판별한다. 물론 (x,y,z), (y,z,x), (z,x,y)는 순서만 다를뿐 회전시키면 같은 모양이기 때문에 이 부분도 고려하여 비교하였다. #include #include #include #include #include #in..
알고리즘 2024. 5. 31. 12:12
백준 17349번 1루수가 누구야 C++ (골드4)

https://www.acmicpc.net/problem/17349 단순해 보이지만 생각할게 은근 많은 문제였다. 우선 선수를 한명씩 지정하여 거짓말을 하고 있다고 가정하고 지정한 선수의 말을 바꿔서 모두 옳은말을 하고 있다고 가정한다. 여기서 두 사람의 말이 다르다면 모순인 상황이고, 바로 스킵해준다. 특정 선수를 1루수라고 주장하는 사람이 1명이라면, 그 경우에서는 주장한 사람이 지정한 선수가 1루수가 맞다.특정 선수를 1루수라고 주장하는 사람이 2명 이상이라면 틀린 경우이다.특정 선수를 1루수라고 주장하는 사람이 0명이라면 8명이 1루수라고 주장하지 않았을때만 나머지 1명이 1루수가 될 수 있다. 즉, 특정 선수를 1루수라고 주장하는 사람이 1명이거나 1루수가 아니라고 주장하는 경우가 8가지 경우일..
알고리즘 2024. 5. 30. 11:13
이전 Prev 1 2 3 4 5 6 ··· 103 Next 다음