본문 바로가기

분류 전체보기414

백준 7812 중앙트리 (Java) 문제 URL : https://www.acmicpc.net/problem/7812  문제 접근법 :모든 노드의  비용의 합을 다구하는 문제입니다.대표적인 트리 dp 문제인데  증명은 https://www.youtube.com/watch?v=T81Bpx2OmS4이 유튜브를 참고하는게 좋을것같습니다. leetcode 문제인데 이문제와 유사하며 거기에 가중치가 있을 뿐입니다. 간단하게 하나의 루트로부터 모든 비용을 구한후 다음 노드에서의 가중치의 합을 구할려면그 가중치로부터  노드의개수가 n일때 n-child의 개수만큼 비용을 똑같이 더해주고 그리고 -child의 개수만큼 빼줘야하는데n- child - child 의 공식이 나옵니다.그래서 가중치를 곱하면 끝입니다. 소스코드 : import java.io.*;.. 2024. 11. 30.
백준 12970 AB 문제 URL : https://www.acmicpc.net/problem/12970 문제 접근법 : 처음엔 전수조사해서 풀려고 했으나 2^50 이라 가능할것같지 않아서수학적으로 접근했습니다. 만약 ABBBBABB 가 있따면뒤에 있는B뒤에있는 B들은 전부 A의 개수만큼 더해줘야하기때문에01111022 가 되는 구조라처음부터 n의 길이만큼 B로 설정해줍니다.그럼 어딘가 k개 이하만큼 A를 잘 설정해줘야하는데n이 6이라고 가정하고 k에 상관없이처음 BBBBBB 로시작해0번째에 A를 놓는다고가정하면ABBBBB 가 되고 011111 만큼 count하면 5가 되고중간 아무 위치에 A를 넣을때 어떻게 카운트하냐면ABABBB일때 010222가 된다면 7이 되는데 A의 인덱스위치에서 n-1-i 만큼 카운트해주고 또 앞에.. 2024. 11. 15.
Softeer GINI야 도와줘 c++ 문제 URL : https://softeer.ai/practice/6271 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 문제 접근법 : bfs를 두번사용하면 되는문제입니다.소나기가 먼저퍼진후, 그다음 시작점에서 끝점까지 갈수있는지 확인하는 단순 bfs문제입니다.처음 할때 실수로 시작점과 끝점을 바꿔서 코딩하다가 1시간넘게 안풀려서 의아했었는데시작포인트와 끝포인트가 달라졌다는것을 깨닫고 풀렸네요 소스코드 : //By 콩순이냉장고#includeusing namespace std;int n,m;vector> board;vector> rv;int sy,sx,fy,fx;int dy[4]={-1,0,1,0};int dx[4]={0,1,0,-1};void input(){ cin>>n>>.. 2024. 11. 15.
Softeer [21년 재직자 대회 예선] 이미지 프로세싱 c++ 문제 URL : https://softeer.ai/practice/6265 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 문제접근법 : 해당좌표에서 좌우상하 같은 색깔이 있다면 그색깔을 원하는색깔로 바꿔 주면되는 문제입니다. dfs or bfs 아무거나 상관없이 다 적용가능합니다. 이연산은 최대 q번 해야하는데그렇다면 방문자 처리를 매번 해당배열 사이즈만큼 만들어도 답은 나오지만 좀더 빠르게하기위해방문자 배열을 한번만 만들고 dfs 를 q번 해야하므로 1번부터 q번까지의 방문자 숫자를 준다면 굳이 여러번 배열을 만들필요가 없습니다. 소스코드 : //By 콩순이냉장고#includeusing namespace std;int n,m,q;vector>board,check;vector> t.. 2024. 11. 15.

티스토리툴바